算法题：topK给出3种解法

[问答题]

算法题：topK给出3种解法

查看答案及解析

MuMaXu

快速排序寻找数组第k小的元素

从数组L[1…n]中选择枢纽pivot(随机地或者直接取第一个)进行和快速排序一样的划分操作后，表L[1…n]被划分为L[1…m-1]和L[m+1…n]，其中L[m]=pivot

讨论m与k的大小关系：

当m=k时，显然pivot就是要寻找到的元素，直接返回pivot就可以
当m<k时，则要寻找的元素一定是在L[m+1…n]中，从而可以对L[m+1…n]递归地查找第k-m小的元素

当m>k时，则要寻找的元素一定是在L[1…m-1]中，从而可以对L[1…m-1]递归地找第k小的元素

int kth_elem(int A[],int low,int high,int k){
int low_temp=low;
int high_temp=high;
int pivot=A[low];
while(low<hihg){
  while(low=pivot) high--;
  while(low<high&&A[low]<=pivot) low++;
}
A[low]=pivot;
if(low==k) return A[low];
if(low>k) return kth_elem(A,low_temp,low-1,k);
if(low<k) return kth_elem(A,low+1,high_temp,k-low);
}

编辑于 2019-06-02 14:38:10 回复(0)

7777gloryglory

第一种，直接排序，寻找前k个值，过于简单不写。

第二种，利用快速排序的思想部分排

class Solution {
public:
    
    int partsort(vector<int>& input, int left, int right) {
        
        int key = input[left];
        
        while(left < right) {
            while(left < right && input[right] >= key) {
                right--;
            }
            input[left] = input[right];
            
            while(left < right && input[left] <= key) {
                left++;
            }
            input[right] = input[left];
        }
        input[left] = key;
        return left;
    }
    
    
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
      
        vector<int> v;
        if(input.size() == 0 || k > input.size()) {
            return v;
        }
        
        int left = 0;
        int right = input.size() - 1;
        int mid = partsort(input, left, right);
     
        while(mid != k - 1) {
            
            if(mid > k - 1) {
                right = mid - 1;
                mid = partsort(input, left, right);
            }
            else {
                left = mid + 1;
                mid = partsort(input, left, right);
            }
        }
        
        input.resize(k);
        sort(input.begin(), input.end());
        
        return input;
    }
};

第三种，构建大根堆

class Solution {
public:
    
    struct cmp {
        bool operator()(int a, int b) {
            return a < b;
        }
    };
    
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        
        vector<int> vec;
        if(input.size() == 0 || k <= 0 || k > input.size()) {
            return vec;
        }
        
        priority_queue<int, vector<int>, cmp> pq;    //构建大根堆
        for(int i = 0; i < input.size(); i++) {
            if(i < k) {
                pq.push(input[i]);
            }
            else {
                if(input[i] < pq.top()) {
                    pq.pop();
                    pq.push(input[i]);
                }        
            }
        }
        
        for(int i = 0; i < k; i++) {
            vec.push_back(pq.top());
            pq.pop();
        }
        return vec;
    }
};

发表于 2020-08-07 21:39:33 回复(0)

提交观点

问题信息

上传者：小小

难度：

2条回答 67收藏 2938浏览

算法题：topK给出3种解法

快速排序寻找数组第k小的元素

问题信息

热门推荐

相关试题