【29】求无序序列中最小k个数

题目：给定一个无序序列和一个数k，求最小k个数（不要求数字有序）

分析：

方案一：最朴素的方法是利用快速排序，然后直接输出最小k个数，时间复杂度为O(nlogn)

方案二：利用快速排序的partition函数的性质，根据基准的性质，每次可以把序列分成两个部分，左边序列全部小于等于基准的值，右边序列全部大于等于序列的值。

              只要找到基准的位置为刚好为第k的位置，则序列前面即为最小k个数。和找第k大的数其实是一个性质的，时间复杂度都是O(n)。

              时间复杂度的证明：

              1. 假设总的元素个数有n个，则

                  第一次枚举n个数

                  第二次枚举n/2

                  第三次枚举n/4

                  ...................1

              2. 则总的时间为n+n/2+n/4+....+1 <= 2n，因此时间复杂度为O(n)

举例：假设序列为0 9 -1 6 7 3 5，最小k个数为-1 0 3

实例代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

//Partition函数
int Partition(int *arrNum, int l, int r){
     //数据不合法
	 if(arrNum == NULL || l > r){
         return -1;
     }
     int mid = (l+r)>>1;
     swap(arrNum[mid], arrNum[r]);
     int leftSeqIndex = l;
     //扫描
	 for(int i = l; i < r; i++){
	     if(arrNum[i] < arrNum[r]){
             if(i > leftSeqIndex){
  			     swap(arrNum[i], arrNum[leftSeqIndex]);
      		 }
      		 ++leftSeqIndex;
         }
     }
     swap(arrNum[leftSeqIndex], arrNum[r]);
     return leftSeqIndex;
} 

//输出最小k个数
void OutputMinKNumber(int *arrNum, int k){
	 for(int i = 0; i < k; i++){
	     cout<<arrNum[i]<<" ";
	 }
	 cout<<endl;
} 

//得到最小k个数
void GetMinKNumber(int *arrNum, int n, int k){
	 //数据不合法
	 if(arrNum == NULL || n <= 0 || k <= 0 || k > n){
        return;
	 }
	 int l = 0;
	 int r = n-1;
	 while(l <= r){
	     int index = Partition(arrNum, l, r);
	     if(index == -1){
       	     return;
		 }
	     if(index+1 == k){
			 OutputMinKNumber(arrNum, k);
			 return;
         }
         else if(index+1 > k){ //左边序列查找
		     r = index-1;
		 }
 	     else{
	         l = index+1;
		 }
	 }
} 

int main(){
    int arrNum[] = {0,9,-1,6,7,3,5};
    GetMinKNumber(arrNum, 7, 3);

    return 0;
}
/*
输出
-1 0 3
*/