基于快排的TOP K 问题

类似于快速排序，首先选择一个划分元，如果这个划分元的序号index刚好等于k，那么这个划分元以及左边的数，刚好组成了top-k small data;如果index>k, 那top-k small data在index的左边，那么就继续递归从index-1和数中选取top-k.如果index < k,那么说明还要从index的右边，选取top-(k-index) small data.

public int quickSort(int[] arr, int start, int end){
    if(start<end){
        int temp = arr[start];
        int low = start;
        int high = end;
        while(low<high){
            while(low<high && arr[high]>= temp){
                high--;
            }
            arr[low] = arr[high];
            while(low<high && arr[low]< temp){
                low--;
            }
            arr[high] = arr[low];
        }
        arr[low] = temp
        return low
    }else{
        return -1;
    }
    
}


public int findTopK(int[] arr, int start, int end, int K){
    int index = 0;
    if(start<end){
        index = quickSort(arr, start,end) ;
        if(index ==k){ //正好找到第K个数
            index = k
        }else if (index <k){//还要从index的右边找k-index个数
            index = quickSort(arr,index +1, end ,k-index);
        }else if (index>k){
            //比如10个数组，k =3  , index = 7
            index = quickSort(arr,start,index-1,k);
        }
    }
    return index;
}

最后

以上就是完美猫咪为你收集整理的基于快排的TOP K 问题的全部内容，希望文章能够帮你解决基于快排的TOP K 问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。