本文共 1990 字，大约阅读时间需要 6 分钟。
题目链接： 剑指offer
题目描述： 给你N个数， 让你求出最小的K个数
解题思路： 求出最小的K个数， 借助快速排序中的Partition函数实现O(n)的复杂度， 有点儿类似于二分的思想， 但是不懂的是， 为什么getLeastNumbers的复杂度是O(n)？一会回实验室问一下
代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include #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("=======\n")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;}
思考： 我喜欢这本书， 有好多技巧， 我在这儿也学到了很多思想， 所以我想刷完这本书， 怎么对于自己都是有好处的
转载于:https://www.cnblogs.com/FriskyPuppy/p/7506450.html
