Median

Tags: LintCode Copyright, Quick Sort, Array, Easy

Question

Problem Statement

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(n \log n), 不符合题目要求。线性时间复杂度的排序算法常见有计数排序、桶排序和基数排序，这三种排序方法的空间复杂度均较高，且依赖于输入数据特征（数据分布在有限的区间内），用在这里并不是比较好的解法。

由于这里仅需要找出中位数，即找出数组中前半个长度的较大的数，不需要进行完整的排序，说到这你是不是想到了快速排序了呢？快排的核心思想就是以基准为界将原数组划分为左小右大两个部分，用在这十分合适。快排的实现见 Quick Sort, 由于调用一次快排后基准元素的最终位置是知道的，故递归的终止条件即为当基准元素的位置(索引)满足中位数的条件时(左半部分长度为原数组长度一半，无论奇偶均是如此)即返回最终结果。在数组长度确定后，我们可以直接套用 K 大数的模板来解，即 K 为 (length + 1) / 2.

Python

  1. class Solution:
  2.     """
  3.     @param nums: A list of integers.
  4.     @return: An integer denotes the middle number of the array.
  5.     """
  6.     def median(self, nums):
  7.         if not nums:
  8.             return -1
  9.         return self.kth(nums, 0, len(nums) - 1, (1 + len(nums)) / 2)
  11.     def kth(self, nums, left, right, k):
  12.         # if left >= right: return nums[right]
  14.         m = left
  15.         for i in xrange(left + 1, right + 1):
  16.             if nums[i] < nums[left]:
  17.                 m += 1
  18.                 nums[m], nums[i] = nums[i], nums[m]
  20.         # swap between m and l after partition, important!
  21.         nums[m], nums[left] = nums[left], nums[m]
  23.         if m + 1 == k:
  24.             return nums[m]
  25.         elif m + 1 > k:
  26.             return self.kth(nums, left, m - 1, k)
  27.         else:
  28.             return self.kth(nums, m + 1, right, k)

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param nums: A list of integers.
  5.      * @return: An integer denotes the middle number of the array.
  6.      */
  7.     int median(vector<int> &nums) {
  8.         if (nums.empty()) return 0;
  10.         int len = nums.size();
  11.         return kth(nums, 0, len - 1, (len + 1) / 2);
  12.     }
  14. private:
  15.     int kth(vector<int> &nums, int left, int right, int k) {
  16.         // if (left >= right) return nums[right];
  18.         int m = left; // index m to track pivot
  19.         for (int i = left + 1; i <= right; ++i) {
  20.             if (nums[i] < nums[left]) {
  21.                 ++m;
  22.                 std::swap(nums[i], nums[m]);
  23.             }
  24.         }
  26.         // swap with the pivot
  27.         std::swap(nums[left], nums[m]);
  29.         if (m + 1 == k) {
  30.             return nums[m];
  31.         } else if (m + 1 > k) {
  32.             return kth(nums, left, m - 1, k);
  33.         } else {
  34.             return kth(nums, m + 1, right, k);
  35.         }
  36.     }
  37. };

Java

  1. public class Solution {
  2.     /**
  3.      * @param nums: A list of integers.
  4.      * @return: An integer denotes the middle number of the array.
  5.      */
  6.     public int median(int[] nums) {
  7.         if (nums == null || nums.length == 0) return -1;
  9.         return kth(nums, 0, nums.length - 1, (nums.length + 1) / 2);
  10.     }
  12.     private int kth(int[] nums, int left, int right, int k) {
  13.         // if (left >= right) return nums[right];
  15.         int m = left;
  16.         for (int i = left + 1; i <= right; i++) {
  17.             if (nums[i] < nums[left]) {
  18.                 m++;
  19.                 swap(nums, i, m);
  20.             }
  21.         }
  22.         // put pivot in the mid position
  23.         swap(nums, left, m);
  25.         if (k == m + 1) {
  26.             return nums[m];
  27.         } else if (k > m + 1) {
  28.             return kth(nums, m + 1, right, k);
  29.         } else {
  30.             return kth(nums, left, m - 1, k);
  31.         }
  32.     }
  34.     private void swap(int[] nums, int i, int j) {
  35.         int temp = nums[i];
  36.         nums[i] = nums[j];
  37.         nums[j] = temp;
  38.     }
  39. }

源码分析

以题目中给出的样例进行分析，k 传入的值可为(len(nums) + 1) / 2, 由于在 kth 入口处 left >= right 之前已经找到解，无需判断。

复杂度分析

和快排类似，这里也有最好情况与最坏情况，平均情况下，索引m每次都处于中央位置，即每次递归后需要遍历的数组元素个数减半，故总的时间复杂度为 O(n (1 + 1/2 + 1/4 + …)) = O(2n), 最坏情况下为平方。使用了临时变量，空间复杂度为 O(1), 满足题目要求。