【LeetCode】面试算法总结@优先队列1、LeetCode----703. 数据流中的第K大元素2、LeetCode----239. 滑动窗口最大值

95 阅读 0 评论 63 点赞

我是靠谱客的博主健壮身影，这篇文章主要介绍【LeetCode】面试算法总结@优先队列1、LeetCode----703. 数据流中的第K大元素2、LeetCode----239. 滑动窗口最大值，现在分享给大家，希望可以做个参考。

面试算法总结：优先队列

1、LeetCode----703. 数据流中的第K大元素
- 基本思路
2、LeetCode----239. 滑动窗口最大值
- 基本思路

1、LeetCode----703. 数据流中的第K大元素

https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/
在这里插入图片描述

基本思路

复制代码

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
#首先保证一个数组里面的个数为k
#通过每次找出数组中的最小的数与新加入的数进行比较
#当新加入的数大于最小的数时将其替换为最小的数，
#最终要求的数为数组中最小的数，返回此数
#最后一个case通不过，由于复杂度大了，当代大神改进此算法
class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.nums = nums
        if len(self.nums) > self.k:
            while len(self.nums) > self.k:
                 self.nums.remove(min(self.nums))
        if not len(self.nums):
            while len(self.nums)!=self.k:
                self.nums.append(-100000)
            
    def add(self, val: int) -> int:
        min_num = min(self.nums)
        if len(self.nums) < self.k:
            self.nums.append(val)
        elif val > min_num:
            self.nums.remove(min_num)
            self.nums.append(val)
        return min(self.nums)

2、LeetCode----239. 滑动窗口最大值

https://leetcode.com/problems/top-k-frequent-words/description/
在这里插入图片描述

基本思路

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#这一题显示是困难，但其实使用python解并不是很难
#首先我们考虑的是遍历整个数组，将内容进行切片处理，每次求解出切片里面最大的元素添加到answer中
#最终返回answer即可，当然需要考虑到一些特殊的情况，比如说数组为空，或者k=1的情况。
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums:
            return
        if k == 1:
            return nums
        answer = []
        for i in range(len(nums)):
            if i+k > len(nums):
                break
            temp = nums[i:i+k]
            answer.append(max(temp))
        return answer