K选取问题

2019/06/16 Algorithm LeetCode

k选取是一个经典的算法问题,找到无序的数组中第k小的数(此处约定最小值为第一小的数)。很容易想到将数组排序,然后取出下标为k-1的元素,该算法的时间复杂度为。显然有更快的方法。

大顶堆法

一个大顶堆维护了弱序关系,堆顶为最大的元素。创建一个大顶堆,遍历数组,如果堆中的元素数量小于,则继续向堆中添加元素;如果堆中的元素数量恰为个,则将堆顶的元素与当前元素进行比较,若当前元素比堆顶小,则删除堆顶元素,将当前元素加入堆中;如果当前元素比堆顶大,则该元素不可能为第k小的数。代码如下:

#include <iostream>
#include <vector>
#include <queue>// header file for priority queue
using namespace std;

int kMinimumEle(vector<int> nums, int k) {
    if (nums.empty() || k < 0 || k > nums.size()) return -1;
    priority_queue<int> heap;
    for (int i = 0; i < nums.size(); i++) {
        if (heap.size() < k) heap.emplace(nums[i]);
        else {
            if (nums[i] < heap.top()) {
                heap.pop();
                heap.emplace(nums[i]);
            } 
        }
    }
    return heap.top();
}

int main()
{
    vector<int> nums = {5, 1, 3, 4, 9, 8, 8, 2};
    for (int i = 1; i <= nums.size(); i++) {
        cout << i << " : " << kMinimumEle(nums, i) << endl;
    }
    system("pause");
    return 0;
}

运行结果:

1 : 1
2 : 2
3 : 3
4 : 4
5 : 5
6 : 8
7 : 8
8 : 9

由于堆的插入、删除操作的时间复杂度为,该算法的时间复杂度为,空间复杂度为.

划分(partition)

quicksort的基础就是对数组进行划分,选取一个轴点(主元),使得比轴点大的数位于左侧,比轴点大的数位于右侧。可以对数组进行划分,当轴点位置等于k-1时,正好找到第k小的元素;若轴点位置比k-1小,说明,第k小的元素在该轴点的右侧;反正在轴点的左侧,代码如下:

#include <iostream>
#include <vector>
#include <cstdlib>// header file for rand
#include <queue>// header file for priority queue
using namespace std;

int partition(vector<int>& nums, int low, int high) {
    if (low < 0 || high >= nums.size() || low > high) return -1;
    if (low == high) return low;
    int index = low + rand() % (high - low + 1);
    swap(nums[index], nums[low]);
    int ele = nums[low];
    while (low < high) {
        while (high > low && (nums[high] >= ele)) high--;
        nums[low] = nums[high];
        while (low < high && (nums[low] <= ele)) low++;
        nums[high] = nums[low]; 
    }
    nums[low] = ele;
    return low;
}

int kMinimumEle(vector<int> nums, int k) {
    k--;
    if (nums.empty() || k < 0 || k > nums.size()) {
        return -1;
    }
    int low = 0, high = nums.size() - 1;
    int index = partition(nums, low, high);
    while (index != k) {
        if (index < k) low = index + 1;
        else high = index - 1;
        index = partition(nums, low, high);
    }
    return nums[index];
}

int main()
{
    vector<int> nums = {5, 1, 3, 4, 9, 8, 8, 2};
    for (int i = 1; i <= nums.size(); i++) {
        cout << i << " : " << kMinimumEle(nums, i) << endl;
    }
    system("pause");
    return 0;
}

运行结果与上述相同。由于在partition中,随机地选取元素作为轴点,所以从期望的角度,该算法的线性复杂度为

Search

    Table of Contents