Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details

describe

Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.

Implement the FreqStack class:

  • FreqStack() constructs an empty frequency stack.
  • void push(int val) pushes an integer val onto the top of the stack.
  • int pop() removes and returns the most frequent element in the stack.
  • If there is a tie for the most frequent element, the element closest to the stack’s top is removed and returned.

Example 1:

Input ["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"] [[], [5], [7], [5], [7], [4], [5], [], [], [], []] Output [null, null, null, null, null, null, null, 5, 7, 5, 4] Explanation FreqStack freqStack = new FreqStack(); freqStack.push(5); // The stack is [5] freqStack.push(7); // The stack is [5,7] freqstack.push (5); // The stack is [5,7,5] freqStack. // The stack is [5,7,5] freqstack.push (4); // The stack is [5,7,5,7,4] freqstack.push (5); // The stack is [5,7,5,7,4,5] freqstack.pop (); // return 5, as 5 is the most frequent. The stack becomes [5,7,5,7,4].freqstack.pop (); // Return 7, as 1 and 2 are the most frequent, but 7 is closest to the top. The stack becomes [5,7,5,4].freqstack.pop ();  // return 5, as 5 is the most frequent. The stack becomes [5,7,4].freqstack.pop (); // Return 4, as 4, 5 and 7 is the most frequent, but 4 is closest to the top. The stack becomes [5,7].Copy the code

Note:

0 <= val <= 10^9
At most 2 * 10^4 calls will be made to push and pop.
It is guaranteed that there will be at least one element in the stack before calling pop.
Copy the code

parsing

This week’s problem is really on the stack, every day is stack, today is no exception, and the difficulty is HARD.

Design a data structure like a stack, push the elements onto the stack, and pop up the elements of frequency from the stack.

Implement the FreqStack class:

  • FreqStack() constructs an empty stack
  • Void push(int val) pushes an integer val to the top of the stack
  • Int pop() removes and returns the most frequently occurring element in a stack, or if there are more than one, the element closest to the top of the stack is removed and returned

The problem is that it’s easy to push elements into the stack, but the hard part is how do we return the element that appears most frequently, or if we have multiple elements that appear most frequently, we delete and return the element closest to the top of the stack. In fact, I started the problem in the wrong direction. I had to use the dictionary to record the number and position of each element, and sort them to realize the logic of returning elements in the problem, which was obviously timed out and complicated to implement.

After I saw the solution method of the BBS bosses to exclaim, clever, because on the one hand, we care about each element of the frequency, on the other hand we should care about again how to maximum frequency element, which defines a group dictionary be from frequency to the frequency of the elements of the stack mapping, we define a global variable maxFreq to maximum frequency, Use the counter C to count the number of occurrences of all elements.

When executing push element x, we add one to c[x] to express it as f, which means the occurrence frequency increases by one, and then judge its relationship with maxFreq. If F is large, maxFreq should be updated to F as the maximum frequency appearing in the stack so far. Otherwise, add x directly to group[f].

Group [maxFreq].pop() = v, and then we decrease c[v] by one to indicate the frequency of v. If group[maxFreq] is empty, then maxFreq can be reduced by one, we can find the related element after the frequency decreased, and finally return v.

Because the whole process is a dictionary operation, the time complexity is O(1) and the space complexity is O(N).

answer

class FreqStack(object):
    def __init__(self):
        self.group = defaultdict(list)
        self.c = collections.Counter()
        self.maxFreq = 0
    def push(self, x):
        self.c[x] += 1
        f = self.c[x]
        if f > self.maxFreq:
            self.maxFreq = f
        self.group[f].append(x)
    def pop(self):
        v = self.group[self.maxFreq].pop()
        self.c[v] -= 1
        if not self.group[self.maxFreq]:
            self.maxFreq -= 1
        return v            	      
		
Copy the code

The results

37/37 Test cases passed. Status: Accepted Runtime: 328 MS Memory Usage: 22.7 MBCopy the code

Original link: leetcode.com/problems/ma…

Your support is my biggest motivation