"能否以O(n)的时间复杂度, 从一个未排序的整数数组中选取第i大的整数出来?"
你面试的时候,有人问过你这样的问题吗?
这类有关大小排序选取的选择问题是极容易出现在面试题目中的问题,在算法学上,我们把这类问题统称为"选择问题", 也称之为"中位数问题".
选择问题的解决, 不一定要先排序然后遍历(事实上这是比较慢的做法,排序的时间复杂度决定了它不可能比O(nlgn)快). 通常选择问题只是要求知道第i大/小的元素, 所以我们可以将它当作排序算法的简化. 我们以快速排序为例, 我们以划分的区间判断,选择问题我们只追究可能出现问题解的一个区间,而快速排序要处理两个区间.
当待选择元素足够均匀时, 本文的RandomizedSelect算法可以达到O(n)的时间复杂度, 而最坏情况下,它的时间复杂度可能是O(n * n).这里有必要着重说明一下, O(n*n)的算法复杂度是RandomizedSelect算法的上限, 而不是它的平均复杂度, 除非是特别设计(样本间元素满足特定关系多项式)的样本, RandomizedSelect算法一般可以认为它的平均时间复杂度是O(n).
算法及解析(偷了个懒,算法的思路写在了代码注释中间)如下:
1: /// <summary>
2: /// 选取第rank小的数
3: /// </summary>
4: /// <param name="array"></param>
5: /// <param name="begin"></param>
6: /// <param name="end"></param>
7: /// <param name="rank"></param>
8: public static int RandomizedSelect(int[] array, int begin, int end, int rank)
9: {
10: if (begin == end)
11: {
12: return array[begin];
13: }
14:
15: //随机选取一个基准元素,将数组按照基准元素值的大小分区,
16: //基准元素的左侧都是比基准元素小的元素
17: //基准元素的右侧都是比基准元素大的元素
18: //返回分区后的基准元素的数组索引
19: int q = RandomizedPartition(array, begin, end);
20:
21: //计算基准元素的数组排位
22: int k = q - begin + 1;
23:
24: if (rank == k)
25: {
26: //分区的基准元素刚好是排在rank位置上, 则直接返回基准元素
27: return array[q];
28: }
29: else if (rank < k)
30: {
31: //分区的基准元素比rank大,转为在基准元素左面的区间中寻找
32: return RandomizedSelect(array, begin, q - 1, rank);
33: }
34: else
35: {
36: //分区的基准元素比rank小,转为在基准元素右面的区间中寻找
37: return RandomizedSelect(array, q + 1, end, rank - k);
38: }
39: }
40:
41: /// <summary>
42: /// 随机分区函数,同样应用于快速排序算法中
43: /// </summary>
44: /// <param name="ary"></param>
45: /// <param name="begin"></param>
46: /// <param name="end"></param>
47: /// <returns></returns>
48: public static int RandomizedPartition(int[] ary, int begin, int end)
49: {
50: Random rm = new Random();
51: int randomIndex = rm.Next(begin, end);
52:
53: //exchange the random-selected element with the last element
54: int tmp = ary[randomIndex];
55: ary[randomIndex] = ary[end];
56: ary[end] = tmp;
57:
58: return Partition(ary, begin, end);
59: }
60:
61:
62: /// <summary>
63: /// 分区函数的一种实现,始终选取最后一个元素作为分区基准
64: /// </summary>
65: /// <param name="ary"></param>
66: /// <param name="begin"></param>
67: /// <param name="end"></param>
68: /// <returns></returns>
69: public static int Partition(int[] ary, int begin, int end)
70: {
71: // take the last element of array for judge point
72: int judgeValue = ary[end];
73:
74: // i is the bound of elements lower than judgeValue.
75: int i = begin -1;
76: for( int j = begin ; j < end ; j ++ )
77: {
78: if (ary[j] <= judgeValue)
79: {
80: //expand the lower bound
81: i += 1;
82:
83: //exchange A[i] with current element.
84: int tmp = ary[i];
85: ary[i] = ary[j];
86: ary[j] = tmp;
87: }
88: }
89:
90: // exchange the judge element with the beginner of larger elements
91: int tmpV = ary[i+1];
92: ary[i+1] = ary[end];
93: ary[end] = tmpV;
94:
95: return i + 1;
96: }
算法的测试程序:
1: static void Main(string[] args)
2: {
3:
4: int[] arraySort = new int[10] { 1,6,7,8,0,3,2,5,4,9};
5:
6: Console.WriteLine("Current array is:");
7: foreach (var item in arraySort)
8: {
9: Console.Write(item + " ");
10: }
11:
12: while (true)
13: {
14: Console.WriteLine("\r\nPlease input the rank which you want to pick up:");
15:
16: string val = Console.ReadLine();
17:
18: if (val.ToLower() == "exit")
19: break;
20: int keyValue = 0;
21: Int32.TryParse(val, out keyValue);
22: Console.WriteLine("\r\n"+RandomizedSelect(arraySort, 0, 9, keyValue));
23: }
24: }