算法训练day12Leetcode239滑动窗口最大值347前k个高频元素

发布时间:2024年01月13日

今日学习文章链接

https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html#%E6%80%9D%E8%B7%AF

239 滑动窗口最大值

题目描述

给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

 

示例 1:

输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
示例 2:

输入:nums = [1], k = 1
输出:[1]
 

提示:

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

我的想法

只想到了暴力解法,n*k的复杂度

题目分析

我们需要一个队列,这个队列呢,放进去窗口里的元素,然后随着窗口的移动,队列也一进一出,每次移动之后,队列告诉我们里面的最大值是什么。

这个队列应该长这个样子:

class MyQueue {
public:
    void pop(int value) {
    }
    void push(int value) {
    }
    int front() {
        return que.front();
    }
};

每次窗口移动的时候,调用que.pop(滑动窗口中移除元素的数值),que.push(滑动窗口添加元素的数值),然后que.front()就返回我们要的最大值。

这么个队列香不香,要是有现成的这种数据结构是不是更香了!

其实在C++中,可以使用 multiset 来模拟这个过程,文末提供这个解法仅针对C++,以下讲解我们还是靠自己来实现这个单调队列。

然后再分析一下,队列里的元素一定是要排序的,而且要最大值放在出队口,要不然怎么知道最大值呢。

但如果把窗口里的元素都放进队列里,窗口移动的时候,队列需要弹出元素。

那么问题来了,已经排序之后的队列 怎么能把窗口要移除的元素(这个元素可不一定是最大值)弹出呢。

其实队列没有必要维护窗口里的所有元素,只需要维护有可能成为窗口里最大值的元素就可以了,同时保证队列里的元素数值是由大到小的。

那么这个维护元素单调递减的队列就叫做单调队列,即单调递减或单调递增的队列。C++中没有直接支持单调队列,需要我们自己来实现一个单调队列

不要以为实现的单调队列就是 对窗口里面的数进行排序,如果排序的话,那和优先级队列又有什么区别了呢。

对于窗口里的元素{2, 3, 5, 1 ,4},单调队列里只维护{5, 4} 就够了,保持单调队列里单调递减,此时队列出口元素就是窗口里最大元素。

此时大家应该怀疑单调队列里维护着{5, 4} 怎么配合窗口进行滑动呢?

设计单调队列的时候,pop,和push操作要保持如下规则:

pop(value):如果窗口移除的元素value等于单调队列的出口元素,那么队列弹出元素,否则不用任何操作
push(value):如果push的元素value大于入口元素的数值,那么就将队列入口的元素弹出,直到push元素的数值小于等于队列入口元素的数值为止
保持如上规则,每次窗口移动的时候,只要问que.front()就可以返回当前窗口的最大值。

我的acm模式代码

#include <vector>
#include <iostream>
#include <deque>



class Solution {
private:
    class MyQueue {
    public:
        std::deque<int> que;
        void pop(int value) {
            if (!que.empty() && value == que.front()) {
                que.pop_front();
            }
        }
        void push(int value) {
            while (!que.empty() && value > que.back()) {
                que.pop_back();
            }
            que.push_back(value);
        }

        int front() {
            return que.front();
        }
    };
public:
    std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
        MyQueue que;
        std::vector<int> result;
        for (int i = 0; i < k; i++) {
            que.push(nums[i]);
        }
        result.push_back(que.front());
        for (int i = k; i < nums.size(); i++) {
            que.pop(nums[i - k]);
            que.push(nums[i]);
            result.push_back(que.front());
        }
        return result;
    }
};

int main() {
    Solution sol;

    // 示例数组和窗口大小
    std::vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;

    // 调用函数并接收结果
    std::vector<int> result = sol.maxSlidingWindow(nums, k);

    // 打印结果
    std::cout << "最大滑动窗口的元素为: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}


347前k个高频元素

题目描述

给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

 

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:

输入: nums = [1], k = 1
输出: [1]
 

提示:

1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的
 

进阶:你所设计算法的时间复杂度 必须 优于 O(n log n) ,其中 n 是数组大小。

我的想法

创建hash表,每个键对应一个元素,值对应元素出现的次数

题目分析

这道题目主要涉及到如下三块内容:

要统计元素出现频率
对频率排序
找出前K个高频元素
首先统计元素出现的频率,这一类的问题可以使用map来进行统计。

然后是对频率进行排序,这里我们可以使用一种 容器适配器就是优先级队列。

什么是优先级队列呢?

其实就是一个披着队列外衣的堆,因为优先级队列对外接口只是从队头取元素,从队尾添加元素,再无其他取元素的方式,看起来就是一个队列。

而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢?

缺省情况下priority_queue利用max-heap(大顶堆)完成对元素的排序,这个大顶堆是以vector为表现形式的complete binary tree(完全二叉树)。

什么是堆呢?

堆是一棵完全二叉树,树中每个结点的值都不小于(或不大于)其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆,小于等于左右孩子就是小顶堆。

所以大家经常说的大顶堆(堆头是最大元素),小顶堆(堆头是最小元素),如果懒得自己实现的话,就直接用priority_queue(优先级队列)就可以了,底层实现都是一样的,从小到大排就是小顶堆,从大到小排就是大顶堆。

本题我们就要使用优先级队列来对部分频率进行排序。

为什么不用快排呢, 使用快排要将map转换为vector的结构,然后对整个数组进行排序, 而这种场景下,我们其实只需要维护k个有序的序列就可以了,所以使用优先级队列是最优的。

题目要求前 K 个高频元素,那么果断用大顶堆啊。

那么问题来了,定义一个大小为k的大顶堆,在每次移动更新大顶堆的时候,每次弹出都把最大的元素弹出去了,那么怎么保留下来前K个高频元素呢。

而且使用大顶堆就要把所有元素都进行排序,那能不能只排序k个元素呢?

所以我们要用小顶堆,因为要统计最大前k个元素,只有小顶堆每次将最小的元素弹出,最后小顶堆里积累的才是前k个最大元素。

大顶堆(也称为最大堆)是一种特殊的完全二叉树。在这种数据结构中,每个父节点的值都大于或等于其子节点的值。这种属性使得大顶堆的根节点总是包含整个堆中的最大值。以下是大顶堆的一些关键特征:

  1. 完全二叉树:大顶堆是一种特殊的完全二叉树,这意味着除了最后一层外,每一层都被完全填满,而最后一层的节点尽可能地集中在左侧。

  2. 父节点的值大于子节点的值:在大顶堆中,每个节点的值都大于或等于其子节点的值。这适用于每个非叶子节点。

  3. 堆顶元素:由于每个父节点的值都大于其子节点,堆的根节点(或称为堆顶)包含了堆中的最大值。

  4. 动态结构:尽管大顶堆是有序的,它并不是完全排序的。当添加新元素或移除堆顶元素时,堆会通过一系列的比较和交换操作(称为堆化)来重新调整结构,以维持大顶堆的性质。

  5. 应用场景:大顶堆常用于实现优先队列,以及在各种算法中,如堆排序、查找最大元素等。

在C++中,大顶堆可以使用标准库中的 priority_queue 来实现,而无需指定比较函数,因为 priority_queue 默认就是一个大顶堆。例如:

#include <iostream>
#include <queue>

using namespace std;

int main() {
    priority_queue<int> maxHeap;

    maxHeap.push(10);
    maxHeap.push(5);
    maxHeap.push(15);

    while (!maxHeap.empty()) {
        cout << maxHeap.top() << " ";
        maxHeap.pop();
    }

    return 0;
}

在这段代码中,priority_queue<int> 定义了一个存储整数的大顶堆,堆顶始终是当前堆中的最大值。

acm模式代码


#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
class Solution {
public:
    class mycomparison {
    public:
        bool operator()(const std::pair<int, int>&lhs,const std::pair<int, int>&rhs) {
            return lhs.second > rhs.second;
        }
    };
    std::vector<int> topKFrequent(std::vector<int>& nums, int k) {
        std::unordered_map<int, int> map; //map<nums[i], times>
        for (int i = 0; i < nums.size(); i++) {
            map[nums[i]]++;
        }
        //定义一个小顶堆,大小为k
        std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, mycomparison> pri_que;
        //用固定大小为k的小顶堆,扫描所有频率的数值
        for (std::unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);
            if (pri_que.size() > k) {
                pri_que.pop();
            }
        }
        //找出前k个高频元素,因为小顶堆先弹出的是最小的,所以倒序来输出到数组
        std::vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
};

int main() {
    Solution sol;

    // 测试数据
    std::vector<int> nums = {1, 1, 1, 2, 2, 3,3,3};
    int k = 2;

    // 调用方法
    std::vector<int> topK = sol.topKFrequent(nums, k);

    // 输出结果
    std::cout << "Top " << k << " frequent elements are: ";
    for (int num : topK) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

在你提供的代码片段中,operator() 函数是作为 mycomparison 类的成员定义的。这个操作符重载使得 mycomparison 类成为一个函数对象(也称为仿函数)。这个函数对象被用作 std::priority_queue 的自定义比较器。让我们详细分析这个操作符的功能和作用:

功能分析

bool operator()(const std::pair<int, int>& lhs, const std::pair<int, int>& rhs) {
    return lhs.second > rhs.second;
}
  • 参数: operator() 接受两个 std::pair<int, int> 类型的参数,通常表示队列中的元素。在这个场景中,每个 pair 可能代表了一个值及其出现的频率。

  • 返回值: 该函数返回一个布尔值,这个布尔值基于两个 pair 对象的 second 元素的比较结果。

  • 比较逻辑: lhs.second > rhs.second。这意味着如果 lhssecond 值大于 rhssecond 值,则返回 true;否则返回 false

std::priority_queue 中的作用

当这个比较器用于 std::priority_queue 时,它决定了队列中元素的顺序。在你的场景中,队列中的元素是 std::pair<int, int> 类型的,通常第一个元素代表实际的值,而第二个元素代表这个值的频率或某种权重。

由于 operator() 是根据 pairsecond 值来进行比较的,这个优先队列会根据 second 值的大小来组织其元素。由于比较器返回 truelhs.second > rhs.second,这意味着优先队列实际上是一个最小堆——即 second 值较小的元素会被放在队列的更前面。

应用场景

在你的 topKFrequent 方法中,这种比较器适合用于找到频率(second 值)最高的 k 个元素。使用这个比较器,优先队列会保持其大小为 k,并始终弹出具有最小频率的元素。这样,当所有元素都被考虑过后,队列中就剩下了频率最高的 k 个元素。

栈与队列总结

可以出一道面试题:栈里面的元素在内存中是连续分布的么?

这个问题有两个陷阱:

陷阱1:栈是容器适配器,底层容器使用不同的容器,导致栈内数据在内存中不一定是连续分布的。
陷阱2:缺省情况下,默认底层容器是deque,那么deque在内存中的数据分布是什么样的呢? 答案是:不连续的,下文也会提到deque。
所以这就是考察候选者基础知识扎不扎实的好问题。

在栈与队列系列中,我们强调栈与队列的基础,也是很多同学容易忽视的点。

使用抽象程度越高的语言,越容易忽视其底层实现,而C++相对来说是比较接近底层的语言。

我们用栈实现队列,用队列实现栈来掌握的栈与队列的基本操作。

接着,通过括号匹配问题、字符串去重问题、逆波兰表达式问题来系统讲解了栈在系统中的应用,以及使用技巧。

通过求滑动窗口最大值,以及前K个高频元素介绍了两种队列:单调队列和优先级队列,这是特殊场景解决问题的利器,是一定要掌握的。

文章来源:https://blog.csdn.net/qq_36372352/article/details/135572882
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。