for some reason, my code is "limit time exceed", and when I'm running on my own complier, It's never stop. Can anybody figure it out how to solve it please?

from typing import List

class Solution:
    def mergeSort(self, nums: List[int], left: int, right: int) -> List[int]:
        if (left == right):
            return [nums[left]]        
        answer = []
        mid = left   (right - left)//2
        leftArr = self.mergeSort(nums, left, mid)
        rightArr = self.mergeSort(nums, mid 1, right)
        
        pointer1, pointer2 = 0 ,0
        while ((pointer1 < len(leftArr)) & (pointer2 < len(rightArr))):
            if (self.hashmap[leftArr[pointer1]] > self.hashmap[rightArr[pointer2]]):
                answer.append(leftArr[pointer1])
                pointer1  = 1
            elif (self.hashmap[leftArr[pointer1]] < self.hashmap[rightArr[pointer2]]):
                answer.append(rightArr[pointer2])
                pointer2  = 1
            elif (self.hashmap[leftArr[pointer1]] == self.hashmap[rightArr[pointer2]]):
                if (leftArr[pointer1] > rightArr[pointer2]):
                    answer.append(leftArr[pointer1])
                    pointer1  = 1
                elif (leftArr[pointer1] < rightArr[pointer2]):
                    answer.append(rightArr[pointer2])
                    pointer2  = 1
        
        while (pointer1 >= len(leftArr)) & (pointer2 < len(leftArr)):
            answer.append(rightArr[pointer2])
            pointer2  = 1
        
        while (pointer1 <= len(leftArr)) & (pointer2 > len(leftArr)):
            answer.append(leftArr[pointer1])
            pointer1  = 1
        
        return answer
        
    
    def frequencySort(self, nums: List[int]) -> List[int]:
        """
        step1: build a hashmap, key is the numbers in array, value is the freqency (N)
        step2: 
            1. sort it first by the assending order of frequency and desending order
        """
        
        hashmap = dict()
        left, right = 0, len(nums)-1
        
        for i in range(0, len(nums)):
            if (nums[i] not in hashmap.keys()):
                hashmap[nums[i]] = 1
            else :
                hashmap[nums[i]]  = 1       
        self.hashmap = hashmap
        
        return self.mergeSort(nums, left, right)

I don't know why it requires me more words, so I type few things there...

CodePudding user response：

Here's the corrected version of your code:

from typing import List

class Solution:
    def mergeSort(self, nums: List[int], left: int, right: int) -> List[int]:
        if (left == right):
            return [nums[left]]        
        answer = []
        mid = left   (right - left)//2
        leftArr = self.mergeSort(nums, left, mid)
        rightArr = self.mergeSort(nums, mid 1, right)
        
        pointer1, pointer2 = 0 ,0
        while ((pointer1 < len(leftArr)) and (pointer2 < len(rightArr))):
            if (self.hashmap[leftArr[pointer1]] < self.hashmap[rightArr[pointer2]]):
                answer.append(leftArr[pointer1])
                pointer1  = 1
            elif (self.hashmap[leftArr[pointer1]] > self.hashmap[rightArr[pointer2]]):
                answer.append(rightArr[pointer2])
                pointer2  = 1
            else: # freq is equal
                if (leftArr[pointer1] >= rightArr[pointer2]):
                    answer.append(leftArr[pointer1])
                    pointer1  = 1
                else:
                    answer.append(rightArr[pointer2])
                    pointer2  = 1
        
        while (pointer1 < len(leftArr)):
            answer.append(leftArr[pointer1])
            pointer1  = 1
        
        while (pointer2 < len(rightArr)):
            answer.append(rightArr[pointer2])
            pointer2  = 1
        
        return answer
        
    
    def frequencySort(self, nums: List[int]) -> List[int]:
        """
        step1: build a hashmap, key is the numbers in array, value is the freqency (N)
        step2: 
            1. sort it first by the assending order of frequency and desending order
        """
        
        hashmap = dict()
        left, right = 0, len(nums)-1
        
        for i in range(0, len(nums)):
            if (nums[i] not in hashmap.keys()):
                hashmap[nums[i]] = 1
            else :
                hashmap[nums[i]]  = 1       
        self.hashmap = hashmap
        
        return self.mergeSort(nums, left, right)

There are a few problems with your current implementation:

1. The time limit exceeded is due to the fact that you don't take care of the case where the frequencies are equal and the numbers are also equal. This happens all the time. If you have 2 threes, the frequency of both is 2 and they are also equal in their total ordering. This is where this error happens:

            elif (self.hashmap[leftArr[pointer1]] == self.hashmap[rightArr[pointer2]]):
                if (leftArr[pointer1] > rightArr[pointer2]):
                    answer.append(leftArr[pointer1])
                    pointer1  = 1
                elif (leftArr[pointer1] < rightArr[pointer2]):
                    answer.append(rightArr[pointer2])
                    pointer2  = 1

Since neither of these 2 cases hits, no pointer is incremented so you are stuck in the while loop.

2. The comparison for the frequency is not according to the problem description. Lower frequencies come first while your code brings the higher to the front.
3. The part where you add the potentially remaining elements of the left or right part in the merge is also not correct. Look at the conditions I made for them and compare with your solution.
4. There may be some other minor errors which you can find by comparing the codes.

Note: I have tried to make the least edits to your code. It can be implemented cleaner, IMO, but since this is a learning process, I thought this approach would be more helpful.