仰望星空

位我上者，灿烂星空；道德律令，在我心中。

0%

topk问题

发表于 更新于 分类于 ，
本文字数： 2.3k 阅读时长 ≈ 2 分钟

【道德经·第二十二章】曲则全，枉则直，洼则盈，敝则新，少则得，多则惑。是以圣人抱一为天下式。不自见，故明；不自是，故彰，不自伐，故有功；不自矜，故长。

最小的k个数

给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。

快速排序解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int partition(vector<int>& nums, int l, int r) {
    int pivot = nums[r];
    int i = l;
    for(int j = l; j < r; j++) {
        if(nums[j] < pivot) {
            swap(nums[i], nums[j]);
            i++;
        }
    }
    swap(nums[i], nums[r]);
    return i;
}
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
    vector<int> res;
    
    if(k<=0 || input.size()<k) return res;
    
    int l = 0, r = input.size()-1;
    while(l <= r) {
        int p = partition(input, l, r);
        if(p+1 == k) {
            return vector<int>(input.begin(), input.begin()+k);
        } else if(p+1 < k) {
            l = p+1;
        } else {
            r = p-1;
        }
    }
    
    return res;
}

堆排序解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
    vector<int> res;
        
    int n = input.size();
    if(k<=0 || n<k) return res;
    // 默认为最大堆，维护最小的k个数    
    priority_queue<int> pq;  
    for(int i = 0; i < n; i++) {
        if(pq.size() < k) {
            pq.push(input[i]);
            continue;
        } else {
            if(input[i] < pq.top()) {
                pq.pop();
                pq.push(input[i]);
            }
        }
    }
        
    while(!pq.empty()) {
        int x = pq.top(); pq.pop();
        res.push_back(x);
    }
        
    return res;
}

寻找第K大

有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。

快速排序解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int partition(vector<int>& nums, int l, int r) {
    // 随机数选枢轴
    int randIdx = l + rand() % (r - l + 1);
    swap(nums[r], nums[randIdx]);
    
    int pivot = nums[r];
    
    int i = l;
    for(int j = l; j < r; j++) {
        if(nums[j] > pivot) {
            swap(nums[i], nums[j]);
            i += 1;
        }
    }
    
    swap(nums[i], nums[r]);
    return i;
}
int findKth(vector<int> a, int n, int K) {
    // write code here
    if(n < K) return -1;
    
    int l = 0, r = n-1;
    while(l <= r) {
        int p = partition(a, l, r);
        if(p == K-1) {
            return a[p];
        } else if(p < K-1) {
            l = p+1;
        } else {
            r = p-1;
        }
    }
    
    return -1;
}

堆排序解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int findKth(vector<int> a, int n, int K) {
    // write code here
    if(n < K) return -1;
    // 小顶堆
    priority_queue<int, vector<int>, greater<int> > pq;
    for(int i = 0; i < n; i++) {
        if(pq.size() < K) {
            pq.push(a[i]);
        } else {
            if(a[i] > pq.top()) {
                pq.pop();
                pq.push(a[i]);
            }
        }
    }
    
    return pq.top();
    
}

位我上者，灿烂星空；道德律令，在我心中。