leetcode 1636.通过python和mergeSort方法通过增加频率对数组进行排序

Question

由于某种原因，我的代码是"如果超过"极限时间"；，当我在自己的编译器上运行时，它永远不会停止。有人能想出怎么解决吗？

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)

我不知道为什么它需要我更多的单词，所以我在那里键入了一些东西。。。

Answer 1

以下是代码的更正版本：

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)

您当前的实现存在一些问题：

1. 超过时间限制是因为您没有考虑频率相等且数字也相等的情况。这种情况经常发生。如果你有两个三，两者的频率都是2，它们的总排序也相等。这就是发生此错误的地方：

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循环中。

2. 频率的比较不符合问题描述。较低的频率优先，而您的代码会将较高的频率带到前面
3. 在合并中添加左侧或右侧部分的潜在剩余元素的部分也不正确。看看我为它们设定的条件，并与您的解决方案进行比较
4. 通过比较代码，您可能会发现其他一些小错误

注意：我试图对您的代码进行最少的编辑。IMO，它可以更清洁地实施，但由于这是一个学习过程，我认为这种方法会更有帮助。