Python 优先级队列-后续弹出 return 第一次弹出后值错误？

Question

我正在尝试使用优先级队列解决 Leetcode #347 前 K 个频繁出现的元素。但是，我的代码在一些测试用例中失败了。

代码如下：

from queue import PriorityQueue
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    counts = {}
    mynums = set()
    q = PriorityQueue()
    for num in nums:
        if num not in counts:
            print(str(num) + " not in counts, setting count to 1")
            counts[num] = 1
            mynums.add(num)
        else:
            print(str(num) + " in counts, adding 1 to count")
            counts[num] = counts[num] + 1
            print(str(num) + " count is now = " +str(counts[num]))
    for num in mynums:
        print("enqueing " + str(num) + " with count " + str(counts[num]))
        q.put(num, -1*counts[num])
    ans = []
    while k > 0:
        cur = q.get()
        print("adding " + str(cur) + " to ans")
        ans.append(cur)
        k = k - 1
    return ans

这是当运行 k = 2 且 nums = [4,1,-1,2,-1,2,3]

时的标准输出

4 not in counts, setting count to 1
1 not in counts, setting count to 1
-1 not in counts, setting count to 1
2 not in counts, setting count to 1
-1 in counts, adding 1 to count
-1 count is now = 2
2 in counts, adding 1 to count
2 count is now = 2
3 not in counts, setting count to 1
enqueing 1 with count 1
enqueing 2 with count 2
enqueing 3 with count 1
enqueing 4 with count 1
enqueing -1 with count 2
adding -1 to ans
adding 1 to ans

为什么我的代码在第二次调用 q.get() 时似乎跳过了 2 作为 return 的入口？

第一次正确 returns -1，但第二次弹出 returns 1 而不是 2。我找不到原因。请帮忙！

Answer 1

PriorityQue 对象并不像您的代码暗示的那样对项目进行排序。你想要做的是： 1- 将 q.put(num, -1*counts[num]) 更改为 q.put((-1 * counts[num], num)) 2- 将 cur = q.get() 更改为 cur = q.get()[1]

Python 优先级队列-后续弹出 return 第一次弹出后值错误？

Python priority queue- subsequent pops return wrong values after first pop?

python

data-structures