You are given an array of integers nums
, there is a sliding window of size k
which is moving from the very left of the array to the very right. You can only see the k
numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
Example 2:
Input: nums = [1], k = 1 Output: [1]
Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length
Input
: [1,3,2,5,8,7] k = 3
Output
: 1 [3,5,8,8]
-
队列头部的元素最大:队列被设计为始终将当前窗口内最大元素的索引放在队头。
-
移除较小元素:如果新加入的元素大于队列中的某些元素,那么这些较小的元素(在队尾)将被移除。
-
队列顺序:队列中的元素(实际上是它们在原数组中的索引)是有序的,从队头到队尾元素的值是递减的。
-
移动滑窗: 当移动的索引大于window size, 踢出 queue 头部元素。
-
用双端队列deque, 注意在维护性质1时(元素前边都比它大),用
while
而不是 "if" 。 -
队列列维护的是
index
而不是 “number” -
当队列首位所对应的index 超出window size, 则踢出,当在window size 范围内则加入最终结果
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
# initialize deque
queue = deque()
res = []
#acquire each index and value by iterating through nums
for i, num in enumerate(nums):
# Notice not "if" here,
# we iterately remove every numbers in the queue,
# that is less than the current one before it
while queue and num >= nums[queue[-1]]:
queue.pop()
# Notice! push current index into queue
queue.append(i)
#remove the first ele if it's outside the window
if queue[0] == i - k:
queue.popleft()
# check if the length at the current position has
# reached the required window size
if i + 1 >= k:
res.append(nums[queue[0]])
return res
-
Time Complexity
: O(n) where n is the number of elements in the array since each element is only pushed into and poped out of deque once. -
Space Complexity
: O(n) as there may be at most n elements in the deque.
Given an integer array nums
and an integer k
, return the k
most frequent elements. You may return the answer in any order.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]
Example 2:
Input: nums = [1], k = 1 Output: [1]
Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
k
is in the range[1, the number of unique elements in the array]
.- It is guaranteed that the answer is unique.
Follow up: Your algorithm's time complexity must be better than O(n log n)
, where n is the array's size.
-
维护一个最大
k 频率
的列表,首先想到可以用模块collections下的Counter 子类,去获取每个数字对应的频率。 如果对它进行排序并抽取最大的k个那么就可以得到结果,时间复杂度O(nlogn) -
Follow up
: 如果要降低复杂度就需要降低logn
,我们不需要n个最大频率 而只需要k个
。考虑最大字样则联想到Heap, Max Heap 和 Min Heap 我们选择 Min Heap 因为需要维护size K,而 min heap 可以轻易弹出最小元素。
-
Solution1 是优化过的,我们使用了
Min-heap
。这里注意两件事 1. Count类似于字典,其key是num 而value则是频率 : for key,value in counts.items()。 -
用python 的heapq 记得带上num: heappush(min_heap(freq, num), 因为最后我们需要返回num 另外当frequency 相同时,将会以num 作为min heap排序标准。
-
len(min_heap) > k 则踢出最小的tuple(freq,num), 留下的就是我们需要的。最后循环处理min_que,留下tuple中的第二个元素。
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
from collections import Counter
from heapq import heappush, heappop
min_heap =[]
# count frequency of each number in nums by Counter
counts = Counter(nums)
#Iterate through counts for each pair(number, frequency)
for num, freq in counts.items():
# push a pair of tuple into heap
heappush(min_heap, (freq, num))
# check if the heap size exceed k
if len(min_heap) > k:
heappop(min_heap)
#extract the top k frequency number(index 2) from tuple
top_k = [pair[1] for pair in min_heap]
# don't forget return the list top_k
return top_k
-
Time Complexity
: O(nlogk), where there are n heap push and pop operations, each taiking O(log k) time. -
Space Complexity
: O(n+k)-> O(n) , n is the size of counter and k is the size of heap. since k is less than n, therefore the space can be O(n)
-
未经过优化 这里用了 collections.Counter()下面的一个方法:
most_common(k)
, 可以获取计数器中频率最高的k个元素和他们的频率。 -
用 ele for ele, fre in counts.most_common(k), 进行循环解包并返回element。最后生成 top_k 列表
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
from collections import Counter
# Use Counter to count the occurrence of each number in nums
counts = Counter(nums)
# Retrieve the top k most frequent elements
# most_common() returns a list of tuples, unpacking them here
top_k = [element for element, count in counts.most_common(k)]
return top_k
Complexity Analysis:
-
Time Complexity
: O(nlogn) -
Space Complexity
: O(n)
Given an array of strings words
and an integer k
, return the k
most frequent strings.
Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.
Example 1:
Input: words = ["i","love","leetcode","i","love","coding"], k = 2 Output: ["i","love"] Explanation: "i" and "love" are the two most frequent words. Note that "i" comes before "love" due to a lower alphabetical order.
Example 2:
Input: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4 Output: ["the","is","sunny","day"] Explanation: "the", "is", "sunny" and "day" are the four most frequent words, with the number of occurrence being 4, 3, 2 and 1 respectively.
Constraints:
1 <= words.length <= 500
1 <= words[i].length <= 10
words[i]
consists of lowercase English letters.k
is in the range[1, The number of unique words[i]]
Follow-up: Could you solve it in O(n log(k))
time and O(n)
extra space?
本打算采用min_heap 方式,但是遇到了很大问题。原因在于在相同frequency 情况下,需要优先选择字典序 lexicographical order
。如果不考虑 follow-up 可以选择 solution 2 的 sorted + lambda 组合。时间复杂度在O(nlogn)。
这种方法最好的地方是用最小堆的形式 min_heap(-freq, word),呈现了最大堆的作用。利用 heapify(List)
建立只有O(n) 的时间复杂度,然后利用最小堆特性,弹出k个最大元素(klogn),并且保持了他们的字典序。Perfect!
from collections import Counter
from heapq import heapify,heappop
class Solution:
def topKFrequent(self, words: List[str], k: int) -> List[str]:
counts = Counter(words)
# Create a heap of tuples. Each tuple contains the negative frequency and the word.
# Using negative frequency turns the min-heap into a max-heap.
heap = [(-freq, word) for word,freq in counts.items()]
# Convert the list into a heap (in-place).
# The negative frequency ensures that the heap behaves like a max-heap.
heapify(heap)
# Pop the top k elements from the heap and return their words.
# heappop returns the smallest item from the heap (highest frequency due to negative values).
return [heappop(heap)[1] for _ in range(k)]
-
Time Complexity
: O(nlogk) -
Space Complexity
: O(n)
from collections import Counter
class Solution:
def topKFrequent(self, words: List[str], k: int) -> List[str]:
counts = Counter(words)
# sort each unique word by frequncy in descending,then alphabetically
top_k = sorted(counts, key = lambda word: (-counts[word] , word))
# return the first k element by slicing [:k]
return top_k[:k]
Complexity Analysis:
-
Time Complexity
: O(nlogn) -
Space Complexity
: O(n)