Day 13 单调|优先队列: 239. 滑窗最大值, 347. 前K高频, 215. 第K大, 4. 寻找两个正序数组的中位数

239. 滑动窗口最大值

思路
- example
- 手动实现单调队列 class
  - que = deque():　左边出，右边进或出
    - que 维护单调下降数列
      - 新加元素大于前面元素，可以把前面元素pop()，因为前面元素不可能成为当前或者下面窗口的最大值。
      - 新加元素小前面元素，append新元素即可。
  - size(que) = k，滑动窗口size = k
  - 每次需要 (先出后进）
    - 移除最左边元素
    - 加进当前位置元素
    - 取que[0]得到当前窗口最大值
复杂度. 时间：O(n), 空间: O(k)

单调队列：先进先出 + 维护最大（小）值

class Mdeque:
    def __init__(self):
        self.que = collections.deque()

    def push(self, val):
        while self.que and val > self.que[-1]: # if val==que[-1], keep both
            self.que.pop()
        self.que.append(val)
    
    def pop(self, val):
        if self.que and self.que[0] == val:
            self.que.popleft()

    def top(self):
        return self.que[0]

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        res = []
        que = Mdeque()
        for i in range(k):
            que.push(nums[i])
        res.append(que.top()) # res.append(que[0]) --- 不work.
        for i in range(k, len(nums)):
            que.pop(nums[i-k])
            que.push(nums[i])
            res.append(que.top())
        return res

另一个版本

[1]
[3]
[3,-1]
[3,-1,-3]
[5]
[5,3]
[6]
[7]

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums, k: int):
        queue = deque()
        result = []
        left = 0
        for right in range(len(nums)):
            #  如果队列不为0 ， 或者当前元素 大于队列里面的元素， 就将queue里面的元素剔除。
            while len(queue) > 0 and nums[right] >= nums[queue[len(queue) - 1]]:
                queue.pop()
            queue.append(right)
            # 如果队列里面的队首元素 在left 的左边，说明已经在窗口外了，剔除。
            if queue[0] < left:
                queue.popleft()

            # 如果已经形成了窗口
            if right + 1 >= k:
                result.append(nums[queue[0]])
                left += 1
        return result

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        que = collections.deque()
        res = []
        for i in range(n):
            while que and nums[que[-1]] <= nums[i]:
                que.pop()
            que.append(i) 
            if i - que[0] + 1 > k:
                que.popleft()
            if i >= k-1:
                res.append(nums[que[0]])
        return res

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums) 
        que = collections.deque() 
        res = []
        for i in range(n):
            num = nums[i] 
            while que and num >= nums[que[-1]]: # !!!
                que.pop() 
            que.append(i)   
            if i - que[0] + 1 > k: # !!!
                que.popleft()  
            if i >= k-1:
                res.append(nums[que[0]])
        return res

347. 前 K 个高频元素

思路
- example
- 用字典统计数字频率
- 把[freq, num]用小顶堆(size=k，以freq为值)维护。
复杂度. 时间： $O(n \log(k))$ , 空间: $O(k)$

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        table = collections.defaultdict(int)
        for num in nums:
            table[num] += 1
        que = []
        for num, freq in table.items():
            heapq.heappush(que, [freq, num])
            if len(que) > k: 
                heapq.heappop(que)
        return [x[1] for x in que]

桶排序
时间 $O(n)$ , 空间 $O(n)$

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        table = collections.defaultdict(int)
        max_freq = 0
        for num in nums:
            table[num] += 1
            max_freq = max(max_freq, table[num])
        table2 = [[] for _ in range(max_freq+1)]
        for num, freq in table.items():
            table2[freq].append(num)
        res = []
        for i in range(max_freq, 0, -1):
            if table2[i]:
                for num in table2[i]:
                    res.append(num)
                    if len(res) == k:
                        return res

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        table1 = collections.defaultdict(int)
        max_freq = 0
        for num in nums:
            table1[num] += 1
            max_freq = max(max_freq, table1[num])
        table2 = collections.defaultdict(list)
        for key, val in table1.items():
            table2[val].append(key) 
        cnt = 0
        res = []
        for i in range(max_freq, -1, -1):
            if table2[i]:
                for num in table2[i]:
                    res.append(num)
                    cnt += 1
                    if cnt == k:
                        return res

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]: 
        table = collections.defaultdict(int)  
        max_freq = 0
        for num in nums:
            table[num] += 1
            max_freq = max(max_freq, table[num])
        table2 = collections.defaultdict(list)  
        for num, freq in table.items():
            table2[freq].append(num)
        cnt = 0
        res = []
        for freq in range(max_freq, -1, -1):
            if len(table2[freq]) > 0:
                while table2[freq]:
                    res.append(table2[freq].pop()) 
                    cnt += 1
                    if cnt == k:
                        return res

215. 数组中的第K个最大元素

思路
- example
- 维护大小为K的小顶堆
复杂度. 时间： $O(n \log(k))$ , 空间: $O(k)$

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        que = []
        for i in range(k):
            heapq.heappush(que, nums[i])
        for i in range(k, len(nums)):
            if nums[i] > que[0]:
                heapq.heappop(que)
                heapq.heappush(que, nums[i])
        return que[0]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        que = []
        for num in nums:
            heapq.heappush(que, num)
            if len(que) > k:
                heapq.heappop(que)
        return que[0]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        n = len(nums)
        que = []
        for i in range(k):
            heapq.heappush(que, nums[i])
        for i in range(k, n):
            if nums[i] > que[0]:
                heapq.heappop(que) 
                heapq.heappush(que, nums[i])
        return que[0]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        n = len(nums) 
        que = [] 
        for i in range(k):
            heapq.heappush(que, nums[i]) 
        for i in range(k, n):
            if nums[i] > que[0]:
                heapq.heappop(que) 
                heapq.heappush(que, nums[i]) 
        return que[0]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        n = len(nums) 
        que = []
        for num in nums:
            if len(que) < k or num > que[0]:
                heapq.heappush(que, num)
            if len(que) > k:
                heapq.heappop(que) 
        return que[0]

其它方法

TBA

4. 寻找两个正序数组的中位数

第k小 (k >= 1), 二分查找

m+n 奇数：k = (m+n)//2 + 1
m+n 偶数：k = (m+n)//2, (m+n)//2+1 --> average
nums1[index1,...,index1+k//2-2], nums2[index2,...,index2+k//2-2] 假设没有越界情况
pivot1 = nums1[index1+k//2-1], pivot2 = nums2[index2+k//2-1]
Case 1: pivot1 <= pivot2, pivot1 不可能是第k小（最多第k-1小），index1 = min(index1 + k//2, m-1) , 更新k继续搜索直到k=1
Case 2: pivot1 > pivot2, pivot2 不可能是第k小（最多第k-1小），index2 = min(index2 + k//2, n-1)，更新k继续搜索直到k=1

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def getKth(nums1, nums2, k):
            index1, index2 = 0, 0 
            while True:
                if index1 == m:
                    return nums2[index2+k-1]
                if index2 == n:
                    return nums1[index1+k-1]
                if k == 1: # 放在这里 
                    return min(nums1[index1], nums2[index2])
                newIndex1 = min(index1+k//2-1, m-1)
                newIndex2 = min(index2+k//2-1, n-1)
                pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]
                if pivot1 <= pivot2:
                    k -= newIndex1 - index1 + 1 # 这个先 
                    index1 = newIndex1 + 1
                else:
                    k -= newIndex2 - index2 + 1
                    index2 = newIndex2 + 1
            # k = 1
            # return min(nums1[index1], nums2[index2]) #  有可能idex1 or index2越界
        m, n = len(nums1), len(nums2) 
        if (m+n) % 2 == 1:
            return getKth(nums1, nums2, (m+n)//2+1)
        else:
            return (getKth(nums1, nums2, (m+n)//2) + getKth(nums1,nums2, (m+n)//2+1)) / 2

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def getKth(k):
            left1, left2 = 0, 0 # !!!
            while k >= 1: 
                if left1 == m: # !!!
                    return nums2[left2+k-1]
                if left2 == n: # !!!
                    return nums1[left1+k-1] 
                if k == 1: # !!!
                    return min(nums1[left1], nums2[left2])
                right1 = min(left1+k//2-1, m-1) # valid index in nums1
                right2 = min(left2+k//2-1, n-1) # valid index in nums2
                pivot1, pivot2 = nums1[right1], nums2[right2]  
                if pivot1 <= pivot2:
                    k -= right1 - left1 + 1
                    left1 = right1 + 1
                else:
                    k -= right2 - left2 + 1
                    left2 = right2 + 1
        m, n = len(nums1), len(nums2)  
        if (m+n) % 2 == 1:
            return getKth((m+n)//2+1) 
        else:
            return (getKth((m+n)//2) + getKth((m+n)//2+1)) / 2

进阶，多个正序数组？

最后编辑于：2023.09.26 11:09:19

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 216,001评论 6赞 498
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,210评论 3赞 392
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 161,874评论 0赞 351
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,001评论 1赞 291
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,022评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,005评论 1赞 295
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,929评论 3赞 416
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,742评论 0赞 271
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,193评论 1赞 309
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,427评论 2赞 331
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,583评论 1赞 346
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,305评论 5赞 342
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,911评论 3赞 325
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,564评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,731评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,581评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,478评论 2赞 352

Day 13 单调|优先队列: 239. 滑窗最大值, 347. 前K高频, 215. 第K大, 4. 寻找两个正序数组的中位数

239. 滑动窗口最大值

347. 前 K 个高频元素

215. 数组中的第K个最大元素

4. 寻找两个正序数组的中位数

推荐阅读更多精彩内容