Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
实现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


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理