- 论坛徽章:
- 0
|
// 找出数组中第K个小的数
//除非你是天才不然就不会写出比我快的了
//最好的算法如下
- #include <iostream>;
- using namespace std;
- void swap(int& a, int& b)
- {
- int temp = a;
- a = b;
- b = temp;
- }
- int k_smallest(int k, int a[], int left, int right)
- {
- int pivot = a[right]; //the last item as pivot
- int i = left;
- int j = right-1;
- for(;;)
- {
- for(; a[i]<pivot; i++);
- for(; a[j]>;=pivot; j--);
- if(i<j)
- swap(a[i], a[j]);
- else
- break;
- }
- swap(a[i], a[right]);
- //now i is the pivot index in the array
- //i.e. a[i] is the (i+1)th smallest item
-
- if(k==i-left+1)
- return a[i];
- else if(k < i-left+1) //target before pivot
- return k_smallest(k, a, left, i-1);
- else //target after pivot
- return k_smallest((k-(i-left+1)), a, i+1, right);
- }
- //find the k_th smallest item in the array
- int Kth_smallest(int k, int a[], int size)
- {
- return k_smallest(k, a, 0, size-1);
- }
- int main()
- {
- int a[10] = {4, 8, 1, 5, 2, 9, 3, 7, 10, 6};
-
- for(int i=1; i<=10; i++)
- cout<<Kth_smallest(i, a, 10)<<" ";
- }
复制代码 |
|