这道题我选用BFS+优先队列来做,(并查集太难了不打算掌握了)。。。
优先队列和普通队列的差别就在于:存到队列中的位置与存的顺序不一定一致,而是由根据存储的权重确定
比如存的权重是[ 2, 3, 1 ],最终的优先队列是[ 1, 2, 3 ]。python里面heappush是最小堆
在本题中的作用就是能够从小到大对query中的数字查询,之后更大的数字可以利用前面小的信息,降低复杂度
因为用优先队列存入每个点的信息,所以直接判断这个队列第一个的权值,如果大于query[ i ],那么后面的节点就不用考虑了
这题看数据知道是一个O(n) or O(nlogn)的算法,注意判断set()中是否存在某个数,复杂度是O(1)...
所以可以直接暴力
标签:周赛,优先,队列,复杂度,LeetCode,323,query,leetcode From: https://www.cnblogs.com/sun-secretbase/p/17011397.html