剑指offer 面试题30 最小的K个数 O(n)

　　题目链接：剑指offer

　　题目描述：给你N个数，让你求出最小的K个数

　　解题思路：求出最小的K个数，借助快速排序中的Partition函数实现O(n)的复杂度，有点儿类似于二分的思想，但是不懂的是，为什么getLeastNumbers的复杂度是O(n)？一会回实验室问一下

　　代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iterator>
#include <cmath>
#include <algorithm>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <queue>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define sca(x) scanf("%d",&x)
#define de printf("=======
")
typedef long long ll;
using namespace std;

int RandomInRange(int s, int e) {
    return rand() % (e-s+1) + s;
}

void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

int Partition(int data[], int len, int start, int end) {
    if( data == NULL || len <= 0 || start < 0 || end >= len ) {
        throw new std::exception();
    }
    int index = RandomInRange(start, end);
    if( index != end ) swap(data[index], data[end]);
    int small = start-1;
    for( int index = start; index < end; index++ ) {
        if( data[index] < data[end] ) {
            small++;
            if( small != index ) {
                swap(data[small], data[index]);
            }
        }
    }
    small++;
    swap(data[small], data[end]);
    return small;
}

void GetLeastNumbers(int *input, int *output, int n, int k) {
    if(input == NULL || output == NULL || n <= 0 || k > n) return;
    int start = 0, end = n-1;
    int index = Partition(input, n, start, end);
    while( index != k-1 ) {
        if( index > k-1 ) {
            index = Partition(input, n, start, index-1);
        }
        else {
            index = Partition(input, n, index+1, end);
        }
    }
    for( int i = 0; i < k; i++ ) {
        output[i] = input[i];
    }
}

void GetAnswer(int *data, int k) {
    for( int i = 0; i < k; i++ ) {
        cout << data[i] << " ";
    }
    cout << endl;
}
int main() {
    int data[10] = {13,32,13,510,5,5,7,78,96,15};
    int output[10];
    GetLeastNumbers(data, output, 10, 5);
    GetAnswer(output, 5);
    return 0;
}

View Code

　　思考：我喜欢这本书，有好多技巧，我在这儿也学到了很多思想，所以我想刷完这本书，怎么对于自己都是有好处的