【28】一个无序的序列查找第K大的数

题目：给定一个无序序列和一个数k，求这个无序序列中第K大的数

分析：

方案一：最朴素的方法利用快速排序然后找到第k个数，时间复杂度O(nlogn)

方案二：根据快速排序中的partition方法，每次可以把一个序列分成两个部分，左边全部小于等于基准，右边的全部大于等于基准。如果partition方法中基准的位置刚好是第k个则可以直接得多这个数，如果大于k说明在左边，如果小于k说明在右边。

              利用这个方法每次可以将序列不断的划分直至找到这第k个数， 因为partition函数的时间复杂度最大为O(n)，而我们每次都可以把序列分成一半，因此总的时间复杂度还是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为3则第k大的数为6。

实例代码：

#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大的数
int GetNumber(int *arrNum, int n, int k){
	//输出-1表示不合法
	if(arrNum == NULL || n <= 0 || k <= 0 || k > n){
        return -1;
    }
    //第k大的数等价于找第n-k+1小的数
	k = n-k+1;
	int l = 0;
	int r = n-1;
	while(l <= r){
	    int index = Partition(arrNum, l, r);
		if(index+1 == k){ //找到
            return arrNum[index];
        }
        else if(index+1 < k){ //在右边序列找
		    l = index+1;
	    }
	    else{ //在左边序列找
	        r = index-1;
	    }
	}
} 

int main(){
   int arrNum[] = {0,9,-1,6,7,3,5};
   int value = GetNumber(arrNum, 7, 3);
   if(value == -1){
       cout<<"no found number";
   }
   else{
       cout<<value<<endl;
   }

   getchar();
   return 0;
}

/*
输出
6
*/