Posted on 2023-03-01 19:01
Uriel 閱讀(74)
評論(0) 編輯 收藏 引用 所屬分類:
閑來無事重切Leet Code 、
Hash 、
排序
實現O(nlogn)的排序，可能有重復的數
因為數據范圍不超過100k，利用python的dict可以實現O(n)，但是空間復雜度就不太好看了
1 #912
2 #Runtime: 710 ms (Beats 84.97%)
3 #Memory: 27.6 MB (Beats 10.48%)
4
5 class Solution(object):
6 def sortArray(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: List[int]
10 """
11 num_dict = defaultdict(lambda:0)
12 min_num = 50001
13 max_num = -50001
14 for i in nums:
15 num_dict[i] += 1
16 min_num = min(min_num, i)
17 max_num = max(max_num, i)
18 ans = []
19 for i in range(min_num, max_num + 1):
20 ans.extend([i] * num_dict[i])
21 return ans