这一篇博客以一些OJ上的题目为载体，讲一下寻找第K小的数的方法
方法一：
先将数据排列好，然后，然后return a[k]或者将前K个数加起来
方法二：
基于高速排序。如，一次高速排序将某一个数放到了第k个位置，那么前k-1个数都要比第k个数小。
后面的数都要比第k个位置上的数要大。所以当前第k个位置上的数就是第K小的数
1、NYOJ 678 最小K个数之和
这道题的时间放得比較松，不要求线性时间，所以用方法一也是能够的
/* * ksmall1.cpp * * Created on: 2014年5月24日 * Author: pc */#include#include #include using namespace std;int main(){ int n,k; while(scanf("%d%d",&n,&k)!=EOF){ int a[n]; int i; for(i = 0 ; i < n ; ++i){ scanf("%d",&a[i]); } sort(a,a+n); int result = 0; for(i = 0 ; i < k ; ++i){ result += a[i]; } printf("%d\n",result); }}
方法二：
#include#include int random(int low, int high) { int size = high - low + 1; return low + rand() % size;}void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp;}int partition(int *a, int left, int right) { int key = a[left]; int i = left; int j; for(j = i + 1; j <= right; j++) { if(a[j] <= key) { if(i != j) { i++; swap(&a[i], &a[j]); } } } swap(&a[i], &a[left]); return i;}int random_partition(int *a, int left, int right) { int index = random(left, right); swap(&a[index], &a[left]); return partition(a, left, right);}int randomized_select(int *a, int left, int right, int k) { if(left < 0 || (right - left + 1) < k) return -1; int pos = random_partition(a, left, right); int m = pos - left + 1; if(k == m) { return pos; } else if(k < m) { return randomized_select(a, left, pos - 1, k); } else { return randomized_select(a, pos + 1, right, k - m); }}int main() { int a[] = {1, 11, 23, 5, 6, 7, 20, 13, 22, 9, 34, 18}; int len = sizeof(a) / sizeof(int); int k = 7; randomized_select(a, 0, len - 1, k); for(int i = 0; i < len; i++) { printf("%d ", a[i]); } printf("\n");}