80.Median-中位数（容易题）

本文主要是介绍80.Median-中位数（容易题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

中位数

1. 题目

   给定一个未排序的整数数组，找到其中位数。

   中位数是排序后数组的中间值，如果数组的个数是偶数个，则返回排序后数组的第N/2个数。

2. 样例

   给出数组[4, 5, 1, 2, 3]， 返回 3

   给出数组[7, 9, 4, 5]，返回 5

3. 挑战

   时间复杂度为O(n)

4. 题解

1.Hashmap法，以空间换时间，时间复杂度为O(n)
先通过一次遍历得到最大值和最小值，并把元素值作为Hashmap的K、把元素出现的次数作为V。
需要注意的是中位数出现的位置应该是：

int count = n % 2 == 1 ? n / 2 + 1 : n / 2;

然后从最小值到最大值对Hashmap进行遍历，每找到一个元素就将count值减1（可以解释为什么count的下标为1而不是0），当count==0时Hashmap的K即是答案。

public class Solution {/*** @param nums: A list of integers.* @return: An integer denotes the middle number of the array.*/public int median(int[] nums) {int min = nums[0];int max = nums[0];int n = nums.length;HashMap<Integer,Integer> hashmap = new HashMap<>();for (int i=0;i<n;i++){int value = hashmap.containsKey(nums[i]) ? hashmap.get(nums[i])+1 : 1;hashmap.put(nums[i],value);min = min < nums[i] ? min : nums[i];max = max > nums[i] ? max : nums[i];}int count = n % 2 == 1 ? n / 2 + 1 : n / 2;for (int i = min;i<=max;i++){while (hashmap.containsKey(i) && hashmap.get(i)>0){--count;hashmap.put(i,hashmap.get(i)-1);if (count == 0){return i;}}}return Integer.MAX_VALUE;//表示出错}
}

2.Top K方法
本题的实质是查找数组中第(n-1)/2大的数，属于Top K问题，即使用快排思想解决问题，时间复杂度是O(n)。

public class Solution {/*** @param nums: A list of integers.* @return: An integer denotes the middle number of the array.*/public int median(int[] nums) {return getMinK(nums,0,nums.length-1,(nums.length-1)/2);}private int getMinK(int[] nums, int left, int right, int k){int i = left;int j = right;while (i != j){while (nums[j] >= nums[left] && i < j){j--;}while (nums[i] <= nums[left] && i < j){i++;}swap(nums,i,j);}swap(nums,left,i);if (i == k){return nums[i];}else if (i < k){return getMinK(nums,i+1,right,k);}else{return getMinK(nums,left,i-1,k);}}private void swap(int[] nums, int i, int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

Last Update 2016.8.31

这篇关于80.Median-中位数（容易题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---