Posted on 2023-03-01 19:01
Uriel 阅读(53)
评论(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