求前k小的数,一般人的想法就是先排序,然后再遍历,但是题目只是求前N小,没有必要完全排序,所以可以想到部分排序,而能够部分排序的排序算法我能想到的就是堆排序和快排了。
第一种思路,局部堆排序。
首先,建立一个大小为N的大顶堆,时间复杂度klgk,然后用其余的数和堆顶元素比较,如果小于堆顶元素则与堆顶元素交换,并进行一次调整,时间复杂度(n-k)lgk,然后klgk可以常数级,(n-k)lgk=O(n)。
第二种思路,利用快排的partition。
只需要稍微修改qsort函数即可,增加判断条件,当partition小于k则快排partition+1到right,如果partition大于k则快排left到partition-1,如果partition等于k,则直接输出数组前k个数,即所求。因为每一轮partition,左部的数都会小于基准数,右部大于基准数 ,所以如果基准下标小于k,说明第k大的数肯定不在基准左部,所以可以缩小搜索条件,直接搜索基准右部,同理基准下标大于k,说明第k大的数肯定不在基准右部,直接搜索基准左部。不过需要注意的一点是qsort中的if(left<right)要改成if(left<right),因为判断partition==k要在下一个递归中。时间复杂度网上证明是O(n)。
public class partitionFindN {
@Test
public void test(){
int[] num = {1,5,9,7,3,4,8,1,6,3,5};
findSmallN(num,8);
} public void findSmallN(int[] num,int n){
Qsort(num,0,num.length-1,n-1);
} public void Qsort(int[] num,int left,int right,int k){
if(left<=right){
int partition = partition(num,left,right);
if(partition==k){
System.out.println("前"+(k+1)+"小的元素为:");
for(int i =0;i<= k;i++){
System.out.print(num[i]+" ");
}
}
else if(partition<k){
Qsort(num,partition+1,right,k);
}
else{
Qsort(num,left,partition-1,k);
}
}
} public int partition(int[] num,int left,int right){
int partition = num[left];
while(left<right){
while(left<right && num[right]>=partition){
right--;
}
swap(num,left,right);
while(left<right && num[left]<=partition){
left++;
}
swap(num,left,right);
}
return left;
} public void swap(int[] num,int m,int n){
int temp = num[m];
num[m] = num[n];
num[n] = temp;
}
}