題目

對于長度為n的整型數(shù)組A，隨機生成其數(shù)組元素值，然后實現(xiàn)一個線性時間的算法，在該數(shù)組中查找其中項。

算法思想

選擇數(shù)組中任意數(shù)作為基準(zhǔn)，將數(shù)組分為大于，小于，等于此數(shù)的三部分，尋找中項。設(shè)小于基數(shù)的個數(shù)為n_small,大于的為n_big,數(shù)組長度的一般為k，若k<=n_s，說明中項在小于基數(shù)的數(shù)組里面，再對small數(shù)組遞歸上述操作，若k=n_s+1，則說明中項就是基數(shù)，若k>n_s+1，說明中項在big數(shù)組里，那么對big數(shù)組遞歸，此時k=k-1-n_s。

代碼

#include <iostream>
#include <vector>
using namespace std;
int select(vector<int>&A, int k,int n)
{
    int x = A[rand() % n];
    vector<int>small;
    small.resize(n);
    vector<int>big;
    big.resize(n);
    int equal,n_s=0,n_b=0;
    for (int i = 0; i < n; i++)
    {
        if (A[i] > x)
            big[n_b++] = A[i];
        else if (A[i] == x)
            equal = x;
        else
            small[n_s++] = A[i];
    }
    if (k <= n_s)
        return select(small, k,n_s);
    else if (k == n_s + 1)
        return equal;
    else
        return select(big, k - 1 - n_s,n_b);
}
int main(void)
{
    vector<int>A;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int temp;
        cin >> temp;
        A.push_back(temp);
    }
    int k = (1 + n) / 2;
    cout << select(A, k,n);
    system("pause");
    return 0;
}