# Median ### Source - lintcode: [(80) Median](http://www.lintcode.com/en/problem/median/) ~~~ Given a unsorted array with integers, find the median of it. A median is the middle number of the array after it is sorted. If there are even numbers in the array, return the N/2-th number after sorted. Example Given [4, 5, 1, 2, 3], return 3 Given [7, 9, 4, 5], return 5 Challenge O(n) time. ~~~ ### 題解 尋找未排序數組的中位數，簡單粗暴的方法是先排序后輸出中位數索引處的數，但是基于比較的排序算法的時間復雜度為 O(nlogn)O(n \log n)O(nlogn), 不符合題目要求。線性時間復雜度的排序算法常見有計數排序、桶排序和基數排序，這三種排序方法的空間復雜度均較高，且依賴于輸入數據特征（數據分布在有限的區間內），用在這里并不是比較好的解法。 由于這里僅需要找出中位數，即找出數組中前半個長度的較大的數，不需要進行完整的排序，說到這你是不是想到了快速排序了呢？快排的核心思想就是以基準為界將原數組劃分為左小右大兩個部分，用在這十分合適。快排的實現見 [Quick Sort](http://algorithm.yuanbin.me/zh-cn/basics_sorting/quick_sort.html), 由于調用一次快排后基準元素的最終位置是知道的，故遞歸的終止條件即為當基準元素的位置(索引)滿足中位數的條件時(左半部分長度為原數組長度一半)即返回最終結果。由于函數原型中左右最小索引并不總是原數組的最小最大，故需要引入相對位置(長度)也作為其中之一的參數。若左半部分長度偏大，則下一次遞歸排除右半部分，反之則排除左半部分。 ### Python ~~~ class Solution: """ @param nums: A list of integers. @return: An integer denotes the middle number of the array. """ def median(self, nums): if not nums: return -1 return self.helper(nums, 0, len(nums) - 1, (1 + len(nums)) / 2) def helper(self, nums, l, u, size): if l >= u: return nums[u] m = l for i in xrange(l + 1, u + 1): if nums[i] < nums[l]: m += 1 nums[m], nums[i] = nums[i], nums[m] # swap between m and l after partition, important! nums[m], nums[l] = nums[l], nums[m] if m - l + 1 == size: return nums[m] elif m - l + 1 > size: return self.helper(nums, l, m - 1, size) else: return self.helper(nums, m + 1, u, size - (m - l + 1)) ~~~ ### C++ ~~~ class Solution { public: /** * @param nums: A list of integers. * @return: An integer denotes the middle number of the array. */ int median(vector<int> &nums) { if (nums.empty()) return 0; int len = nums.size(); return helper(nums, 0, len - 1, (len + 1) / 2); } private: int helper(vector<int> &nums, int l, int u, int size) { // if (l >= u) return nums[u]; int m = l; // index m to track pivot for (int i = l + 1; i <= u; ++i) { if (nums[i] < nums[l]) { ++m; int temp = nums[i]; nums[i] = nums[m]; nums[m] = temp; } } // swap with the pivot int temp = nums[m]; nums[m] = nums[l]; nums[l] = temp; if (m - l + 1 == size) { return nums[m]; } else if (m - l + 1 > size) { return helper(nums, l, m - 1, size); } else { return helper(nums, m + 1, u, size - (m - l + 1)); } } }; ~~~ ### Java ~~~ public class Solution { /** * @param nums: A list of integers. * @return: An integer denotes the middle number of the array. */ public int median(int[] nums) { if (nums == null) return -1; return helper(nums, 0, nums.length - 1, (nums.length + 1) / 2); } // l: lower, u: upper, m: median private int helper(int[] nums, int l, int u, int size) { if (l >= u) return nums[u]; int m = l; for (int i = l + 1; i <= u; i++) { if (nums[i] < nums[l]) { m++; int temp = nums[m]; nums[m] = nums[i]; nums[i] = temp; } } // swap between array[m] and array[l] // put pivot in the mid int temp = nums[m]; nums[m] = nums[l]; nums[l] = temp; if (m - l + 1 == size) { return nums[m]; } else if (m - l + 1 > size) { return helper(nums, l, m - 1, size); } else { return helper(nums, m + 1, u, size - (m - l + 1)); } } } ~~~ ### 源碼分析 以相對距離(長度)進行理解，遞歸終止步的條件一直保持不變(比較左半部分的長度)。 以題目中給出的樣例進行分析，`size` 傳入的值可為`(len(nums) + 1) / 2`, 終止條件為`m - l + 1 == size`, 含義為基準元素到索引為`l`的元素之間(左半部分)的長度(含)與`(len(nums) + 1) / 2`相等。若`m - l + 1 > size`, 即左半部分長度偏大，此時遞歸終止條件并未變化，因為`l`的值在下一次遞歸調用時并未改變，所以仍保持為`size`; 若`m - l + 1 < size`, 左半部分長度偏小，下一次遞歸調用右半部分，由于此時左半部分的索引值已變化，故`size`應改為下一次在右半部分數組中的終止條件`size - (m - l + 1)`, 含義為原長度`size`減去左半部分數組的長度`m - l + 1`. ### 復雜度分析 和快排類似，這里也有最好情況與最壞情況，平均情況下，索引`m`每次都處于中央位置，即每次遞歸后需要遍歷的數組元素個數減半，故總的時間復雜度為 O(n(1+1/2+1/4+...))=O(2n)O(n (1 + 1/2 + 1/4 + ...)) = O(2n)O(n(1+1/2+1/4+...))=O(2n), 最壞情況下為平方。使用了臨時變量，空間復雜度為 O(1)O(1)O(1), 滿足題目要求。