Skip to content

Latest commit

 

History

History
356 lines (231 loc) · 12.6 KB

Day13-Stack and Queue-Part3.md

File metadata and controls

356 lines (231 loc) · 12.6 KB

Day13 - Stack and Queue Part 3

Contents


Day13


Hard

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

Breakdown and Thought Process:


Input: [1,3,2,5,8,7] k = 3

Output: 1 [3,5,8,8]

Day13

Animated demonstration
Day13

维护一个queue 保持下面几个特性:
  1. 队列头部的元素最大:队列被设计为始终将当前窗口内最大元素的索引放在队头。

  2. 移除较小元素:如果新加入的元素大于队列中的某些元素,那么这些较小的元素(在队尾)将被移除。

  3. 队列顺序:队列中的元素(实际上是它们在原数组中的索引)是有序的,从队头到队尾元素的值是递减的。

  4. 移动滑窗: 当移动的索引大于window size, 踢出 queue 头部元素。

Solving approach 1:

  1. 用双端队列deque, 注意在维护性质1时(元素前边都比它大),用 while 而不是 "if"

  2. 队列列维护的是index 而不是 “number”

  3. 当队列首位所对应的index 超出window size, 则踢出,当在window size 范围内则加入最终结果

My Solution 1:Monotonic deque

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.


dividing line

Medium

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.


Breakdown and Thought Process:

  1. 维护一个最大k 频率的列表,首先想到可以用模块collections下的Counter 子类,去获取每个数字对应的频率。 如果对它进行排序并抽取最大的k个那么就可以得到结果,时间复杂度O(nlogn)

  2. Follow up: 如果要降低复杂度就需要降低logn,我们不需要n个最大频率 而只需要k个。考虑最大字样则联想到Heap, Max Heap 和 Min Heap 我们选择 Min Heap 因为需要维护size K,而 min heap 可以轻易弹出最小元素。

Solving approach: O(nlogk)

  1. Solution1 是优化过的,我们使用了 Min-heap。这里注意两件事 1. Count类似于字典,其key是num 而value则是频率 : for key,value in counts.items()。

  2. 用python 的heapq 记得带上num: heappush(min_heap(freq, num), 因为最后我们需要返回num 另外当frequency 相同时,将会以num 作为min heap排序标准。

  3. len(min_heap) > k 则踢出最小的tuple(freq,num), 留下的就是我们需要的。最后循环处理min_que,留下tuple中的第二个元素。

My Solution 1:heapq(min heap)

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)


Solving approach 2: O(nlogn)

  1. 未经过优化 这里用了 collections.Counter()下面的一个方法: most_common(k), 可以获取计数器中频率最高的k个元素和他们的频率。

  2. 用 ele for ele, fre in counts.most_common(k), 进行循环解包并返回element。最后生成 top_k 列表

My Solution 2:most_common(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)


dividing line

Medium


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?


Breakdown and Thought Process:

本打算采用min_heap 方式,但是遇到了很大问题。原因在于在相同frequency 情况下,需要优先选择字典序 lexicographical order 。如果不考虑 follow-up 可以选择 solution 2 的 sorted + lambda 组合。时间复杂度在O(nlogn)。

Solving approach 1: O(nlogk)

这种方法最好的地方是用最小堆的形式 min_heap(-freq, word),呈现了最大堆的作用。利用 heapify(List) 建立只有O(n) 的时间复杂度,然后利用最小堆特性,弹出k个最大元素(klogn),并且保持了他们的字典序。Perfect!

My Solution 1:heapify + min-heap(max heap)

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)


My Solution 2:sorted + lambda

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)


dividing line