Description

給定線性序集中n個元素和一個整數k，n<=2000000，1<=k<=n，要求找出這n個元素中第k小的數。

Input

第一行有兩個正整數n,k.
接下來是n個整數（0<=ai<=1e9）。

Output

輸出第k小的數

Sample Input

6 3 1 3 5 2 4 6

Sample Output

3

利用快速排序可以找出第k小的，加上隨機函數改進一下：
AC代碼：

#include <cstdio> #include <cstdlib> #include <ctime> #include <iostream>int num[2000001];void quictSort(int, int, int); int partition(int, int);int main() {int n, m, i;srand(unsigned(time(NULL))); // 隨機函數種子while (~scanf("%d%d", &n, &m)){for (i = 0; i < n; i++)scanf("%d", &num[i]);quictSort(0, n - 1, m - 1);printf("%d\n", num[m - 1]);}return 0; } // 快速排序 void quictSort(int left, int right, int mTop) {if (left < right){int p = partition(left, right); // 分為兩段if (p == mTop) // 如果隨機找到第mTop小就直接返回return;if (p < mTop)quictSort(p + 1, right, mTop); // 找到的位置比mTop小就在[p + 1, right]區間找if (p > mTop)quictSort(left, p - 1, mTop); // 找到的位置比mTop大就在[left, p - 1]區間找} } // 從小到大排 int partition(int left, int right) {int r = rand() % (right - left + 1) + left; // 隨機選擇一個數int key = num[r];std::swap(num[r], num[left]); // 交換到數組首位while (left < right){// 從數組后面開始, 找比隨機選擇的數小的, 然后從前找比隨機選擇的數大的while (left < right && num[right] >= key)right--;if (left < right)num[left] = num[right];while (left < right && num[left] <= key)left++;if (left < right)num[right] = num[left];}num[left] = key; // 將隨機選擇的數存回return left; // 返回隨機選擇的數分割數組的下標, 左邊都是比它小的, 右邊都是比它大的 }

中位數法線性時間選擇劃分：

AC代碼：

#include <cstdio> #include <cstdlib>int num[2000001];int select(int low, int high, int top); int partition(int low, int high, int median); void selectSort(int low, int high); void swap(int &a, int &b);int main() {int n, m, i;while (~scanf("%d%d", &n, &m)){for (i = 0; i < n; i++)scanf("%d", &num[i]);printf("%d\n", select(0, n - 1, m - 1));/*for (i = 0; i < n; i++)printf("%d%c", num[i], i < n - 1 ? ' ' : '\n');*/}return 0; } // 中位數法線性時間選擇 int select(int low, int high, int top) {// 小于75個數據隨便用一個排序方法if (high - low < 74){selectSort(low, high); // 選擇排序return num[low + top]; // 排完序直接返回第low + top的數}int groupNum = (high - low - 4) / 5; // 每組5個數, 計算多少個組, 從0開始計數for (int i = 0; i <= groupNum; i++){int start = low + 5 * i; // 每組的起始位置int end = start + 4; // 每組的結束位置for (int j = 0; j < 3; j++) // 從小到大冒3個泡for (int k = start; k < end - j; k++)if (num[k] > num[k + 1])swap(num[k], num[k+1]);swap(num[low + i], num[start + 2]); // 每組的中位數交換到前面第low + i的位置}// 上面排完后, 數組low + 0 到 low + groupNum都是每一組的中位數int median = select(low, low + groupNum, (groupNum + 1) / 2); // 找中位數的中位數int p = partition(low, high, median); // 將數組分為兩段, 左邊的小于中位數的中位數, 右邊的大于中位數的中位數int n = p - low; // 計算p到low之間有多少個數, 后面得減掉if (n == top)return num[p]; // 如果運氣好, 剛好要找的就是中位數if (n > top)return select(low, p - 1, top); // n比top大就在左邊找if (n < top)return select(p + 1, high, top - n - 1); // n比top小就在右邊找, 并且top要減去已經大的個數 } // 以中位數進行分割, 分成兩半 int partition(int low, int high, int median) {int p;for (int i = low; i <= high; i++)if (num[i] == median){p = i;break;}// 將中位數交換到最前面swap(num[p], num[low]);// 記下最前面的數int key = num[low];// 把小于key的放前面, 大于key的放后面while (low < high){while (num[high] >= key && low < high)high--;if (low < high)num[low] = num[high];while (num[low] <= key && low < high)low++;if (low < high)num[high] = num[low];}// 分別從兩頭開始, 找到中間時, 把key存回num[low] = key;return low; } // 選擇排序 void selectSort(int low, int high) {for (int i = low; i <= high; i++){int MIN = i;for (int j = i + 1; j <= high; j++)if (num[MIN] > num[j])MIN = j;swap(num[i], num[MIN]);} } // 交換兩個元素 void swap(int &a, int &b) {int temp = a;a = b;b = temp; }

總結

以上是生活随笔為你收集整理的算法：线性时间选择(C/C++)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。