首页 > 代码库 > Median
Median
O(n) worst, O(nlogn) average. Use quickSort
This is quickSort
public class Solution { /** * @param nums: A list of integers. * @return: An integer denotes the middle number of the array. */ public int median(int[] nums) { // write your code here if (nums == null || nums.length == 0) { return 0; } quickSort(nums, 0, nums.length - 1); return nums[(nums.length - 1) / 2]; } private void quickSort(int[] nums, int start, int end) { if (start >= end) { return; } int left = start; int right = end; int pivot = nums[start + (end - start) / 2]; while (left <= right) { while (left <= right && nums[left] < pivot) { left++; } while (left <= right && nums[right] > pivot) { right--; } if (left <= right) { int tmp = nums[left]; nums[left] = nums[right]; nums[right] = tmp; left++; right--; } } quickSort(nums, start, right); quickSort(nums, left, end); } }
Median
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。