首页 > 其他分享 >代码随想训练营第十三天(Pyhton)| 239. 滑动窗口最大值、347.前 K 个高频元素

代码随想训练营第十三天(Pyhton)| 239. 滑动窗口最大值、347.前 K 个高频元素

时间:2023-10-23 20:44:53浏览次数:54  
标签:queue heapq min self list Pyhton 347 heap 第十三天

239. 滑动窗口最大值

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        res = []
        tmp = MyQueue()
        for i in range(k):
            tmp.push(nums[i])
        res.append(tmp.front())            
        for j in range(k, len(nums)):
            tmp.pop(nums[j-k])
            tmp.push(nums[j])
            res.append(tmp.front())
        return res

class MyQueue:

    from collections import deque

    def __init__(self):
        self.queue = deque()   # 这里使用 list 会超出限制

    def pop(self, val):
        if self.queue and val == self.queue[0]:
            self.queue.popleft()

    def push(self, val):
        while self.queue and val > self.queue[-1]:
            self.queue.pop()
        self.queue.append(val)

    def front(self):
        return self.queue[0]

list是Python内置的动态数组类型,它可以存储任意类型的对象,并且可以根据需要动态调整大小。list具有灵活的索引、切片和操作方法,可以方便地进行元素的插入、删除和修改。然而,当需要从列表的头部频繁地插入和删除元素时,list的性能可能会较低,因为这涉及到移动其他元素的操作。

deque(Double-ended Queue,双端队列)是Python标准库collections模块中提供的数据结构。它是一个双端队列,支持从队列的两端高效地进行插入和删除操作。与list相比,deque在执行头部操作(插入和删除)时具有更高的性能,因为它使用了一种双向链表的数据结构。如果你需要在列表的两端频繁地进行插入和删除操作,那么使用deque可能会更高效。

347.前 K 个高频元素

import heapq
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        res = []
        a_map = {}
        for i in nums:
            a_map[i] = a_map.get(i, 0) + 1

        min_heap = []

        for key, val in a_map.items():
            heapq.heappush(min_heap, (val, key))
            if len(min_heap) > k:
                heapq.heappop(min_heap)

        for j in range(k-1, -1, -1):
            res.append(heapq.heappop(min_heap)[1])
        return res

Python提供了heapq模块,其中包含了对堆操作的支持。通过heapq模块,可以轻松地创建和操作堆数据结构,包括插入元素、删除元素、获取最小(或最大)元素等操作。

下面是一个简单的示例,展示了如何使用heapq模块来创建和操作堆:

import heapq

# 创建一个空的堆
heap = []

# 向堆中插入元素
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
heapq.heappush(heap, 1)

# 从堆中弹出最小元素
min_element = heapq.heappop(heap)
print(min_element)  # 输出: 1

# 获取堆中最小元素(不弹出)
min_element = heap[0]
print(min_element)  # 输出: 3

# 将列表转换为堆
my_list = [9, 2, 6, 4, 8]
heapq.heapify(my_list)
print(my_list)  # 输出: [2, 4, 6, 9, 8]

标签:queue,heapq,min,self,list,Pyhton,347,heap,第十三天
From: https://www.cnblogs.com/yixff/p/17783423.html

相关文章

  • P3477 [POI2008] PER-Permutation 解题报告
    我咕咕咕了这道题半年之久?好像洛谷好多题解都被hack了啊,但是没有被撤。(本题解现有hack均通过)题目链接折叠题干[POI2008]PER-Permutation题目描述Multisetisamathematicalobjectsimilartoaset,buteachmemberofamultisetmayhavemorethanonemem......
  • 学习C语言的第十三天
    用递归的方法计算n的阶乘#include<stdio.h>intmain(){intn=0;intmul=1;scanf("%d",&n);for(inti=1;i<=n;i++){mul=mul*i;}printf("%d\n",mul);return0;}以上代码是直接算n的阶乘#include<stdio.h>int......
  • 推荐源哥和川川的新书:《Pyhton网络爬虫从入门到实战》
    ❤️作者主页:小虚竹❤️作者简介:大家好,我是小虚竹。2022年度博客之星评选TOP10......
  • 代码随想录算法训练营day13| ● 239. 滑动窗口最大值 ● 347.前 K 个高频元素 ● 总结
    239.滑动窗口最大值mydemo--(自己思路)--failed超出时间限制classSolution{public:vector<int>maxSlidingWindow(vector<int>&nums,intk){vector<int>result;stack<int>stack;intlen=nums.size();for(......
  • 《看了受制了》第十三天,4道题,合计57道题
    2023年9月11日前面几天去建模,虽然感觉根本过不了。。。。。哎,我们继续回归受制了系列。最近也会总结知识。今天是第二次AK周赛。ACWING5148字符串匹配题目理解,本题是个贪心。题目一点是B串可以随意调整顺序,那就非常EZ了。我们只需要进行对A串B串做一个字符出现次数的统计先......
  • LeetCode347——前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<=10e5k 的取值范围是 [......
  • 基于opencv-pyhton与opencv-c++的结合理解与学习
    2023年上半年,一直在学习opencv-c++版本,学习了其中的多个库函数笔记链接:https://www.cnblogs.com/Tan-code/category/2339311.htmlopencv-python读取图片,画圆等基本操作:opencv-c++多个库函数:opencv-python与opencv-c++结合理解:结合两段代码来比较实现:#导入所需模块......
  • pyhton解决高并发问题
    pyhton解决高并发问题#前端: 1.cdn加速,就是内容分发网络,简单来说就是把静态资源放到别的服务器上 2.精灵图:就是一个大的图片上面有多个我们需要的小图,用定位的方法,定位到不同的小图,满足我们的需求。这样一个请求拿到的图就可以用在多个位置。3.前端缓存:在返回的响应头里......
  • 代码随想录算法训练营第十三天|单调数列:滑动窗口最大值(力扣239.)、优先级队列:前k个高
    单调数列:滑动窗口最大值(力扣239.)给定滑动窗口的范围,求每个滑动窗口范围内的最大值使用单调队列实现对于最大值数字前面的数字不存入数列,对于最大值数字后面的数字存入数列中单调队列中数字的大小呈递减顺序pop(value):如果窗口移除的元素等于单调队列的队口元素,则pop;否则什......
  • HDU 3478
    CatchTimeLimit:2000/1000MS(Java/Others)  MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):1389  AcceptedSubmission(s):682ProblemDescriptionAthiefisrunningaway!Wecanconsiderthecitywherehelocatesasanundirectedgrap......