leetcode-sorting

countSort.py

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