問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2388思路:
1. 排序
這題直接用快排就能AC，很水...
2. 求解第i個順序統計量(詳見CLRS)
利用快速排序過程中的思路，期望時間復雜度是O(n)
ps: partition函數的執行過程是比較有意思的呵呵
1 int
2 partition(long *arr, int begin, int end)
3 {
4 int i, j;
5 i = begin;
6 long pivot = arr[begin];
7 for(j=begin+1; j<=end; j++)
8 if(arr[j] <= pivot)
9 swap(arr, ++i, j);
10 swap(arr, i, begin);
11 return i;
12 }
13
14 long
15 find_ith_os(long *arr, int begin, int end, int ith)
16 {
17 if(begin == end)
18 return arr[begin];
19 int p = partition(arr, begin, end);
20 int k = p-begin+1;
21 if(k == ith)
22 return arr[p];
23 else if(ith < k)
24 return find_ith_os(arr, begin, p-1, ith);
25 else
26 return find_ith_os(arr, p+1, end, ith-k);
27 }