Skip to content

Instantly share code, notes, and snippets.

@liyunrui

liyunrui/countSort.py

Last active Nov 30, 2020
Embed
What would you like to do?
leetcode-sorting
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
return self.countSort(nums)
def countSort(self, A):
"""
It's integer sorting
T: O(n+k), n is nb of data in nums and k is range between in min and max.
S: O(c) in the way we implemented( c is nb of unique elements)
Note:
1.for counting sort, best, average and worst complexity are same-> O(n+k)
2.因為假設我要排 1, 2, 100 這樣 n=3, k=100
"""
mini = min(A)
maxi = max(A)
# O(n)
c = collections.Counter(A)
i = 0
for k in range(mini, maxi+1):
while c[k]:
A[i] = k
i += 1
c[k] -= 1
return A
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.