Thorray

Leetcode题解I

2019/12/15

Leetcode 题解（堆部分）

做题时间2019年12月12日到2019年12月15日

数组中的第K个最大元素

利用最小堆，创建K大小的堆，当堆中元素个数超过K，则删除第K+1个元素。

在代码中使用prpriority_queue<int, vector<int>, greater<int>>，堆中维持K个最大数。

每次循环想堆中加入一个元素，与堆中最小元素比较，遍历vector中所有元素，返回堆顶值。

具体代码如下：

int findKthLargest(vector<int>& nums, int k)
{
    int length = nums.size();
    if (length == 0 || k > length)
    {
        return 0;
    }
    ##创建优先队列
    priority_queue<int, vector<int>, greater<int> > heap;
    for (int i = 0; i < length; i++)
    {
        heap.push(nums[i]);
        if(heap.size()>k)
        {
            heap.pop();
        }
    }
    return heap.top();
}

对于priority_queue<int, vector<int>, greater<int>>

  • 头文件是#include
  • 模板申明3个参数<Type, Container, Functional>, Container必须用数组实现的容器，比如vector, deque等，但不可以使用list。STL中默认使用vector。
  • 对于priority_queue,无法获取某个特定位置的值，只可通过.pop()，.push()以及.top()进行操作。

丑数II

利用最小堆，对丑数创建最小堆。由于丑数是只包含质因数 2, 3, 5 的正整数，但由于题目中要求需要获取第N小的丑数。除了获取所有的丑数后，再次进行排序，选择第N小的丑数。我的做法是，每次选择最小的丑数，对他进行乘2，乘3以及乘5的操作。由于在priority_queue中，我们始终满足堆中的顺序由小到大的排序，所以避免了乱序问题的发生。

但是在计算的过程中由于乘法的交换律，比如2乘3与3乘2，我们可能在两次不同的处理前堆顶得到相同的值，故我们需要对这种情况进行处理。

具体代码如下：

int nthUglyNumber(int n) 
{
    priority_queue<long long, vector<long long>, greater<long long> >heap;
    heap.push(1);
    //因为1不算是丑数
    int length = 0;
    long temp = 0;
    while(length < n)
    {
        if(temp != heap.top())
        {
            temp = heap.top();
            heap.push(temp*2);
            heap.push(temp*3);
            heap.push(temp*5);
            length++;
        }
        //如果遇见了堆顶是一样的值，则我们直接将堆顶的数删除
        else
        {
            heap.pop();
        }
    }
    return heap.top();        
}

这道题除了使用堆的方法进行计算，还可以用动态规划的方法来解决，具体解决方法，将在动态规划部分给出。

超级丑数

与丑数II问题相同，只需将每次与temp相乘的2，3，5替换为质数集合里面的质数值即可。

前K个高频元素

该题，如果K=1，则问题很简单解决，在线性时间内就可以解决，只需要用hash表维护元素出现的频率即可，每一步更新最高频元素。

当K>1时，需要一个能够根据出现频率快速获取元素的数据结构，即优先队列。

首先简历一个元素值对应出现频率的哈希表，这个步骤需要 O(N)时间其中 N 是列表中元素个数。第二步建立堆，堆中每一个元素的复杂度是O(log(k))，进行N次复杂度是O(N)，最后一步输出结果。

在写代码的过程中遇到了一个问题，在建立Hash map的时候，调用了C++内置的map,hash map的范围是从最小元素到最大元素（包括出现频次为0的元素），所以在时间复杂度上并不是O(N)。该问题仍需解决。

vector<int> topKFrequent(vector<int>& nums, int k) {
    int length = nums.size();
    map<int, int>hash;
    //针对nums中的每一个元素在hash中，构建一个它对应的频次
    for(int i = 0; i < length; i++)
    {
        hash[nums[i]]++;
    }
    int max_vec = INT_MIN;
    int min_vec = INT_MAX;
    //找到hash的范围
    for(int i = 0; i < length ;i++)
    {
        if(nums[i] > max_vec)
            max_vec = nums[i];
        if(nums[i] < min_vec)
            min_vec = nums[i];
    }

    priority_queue<int,vector<int>,less<int> >heap;
    for(int i = min_vec; i <= max_vec;i++)
    {
        heap.push(hash[i]);
    }
    vector<int> res_times;
    vector<int> res;
    for(int i = 0; i < k; i++)
    {
        res_times.push_back(heap.top());
        heap.pop();
    }
    for(int j = 0; j < k; j++)
    {
        for(int i = min_vec; i <= max_vec; i++)
        {
            if(res_times[j] == hash[i])
            {
                res.push_back(i);
                hash[i] = 0;
            }
        }
    }
    return res;
}

Post Directory