Radix Sort O(n) solution


  • 0

    It seems that test cases don't contain cases with negative integers. Not considering negative integers, we have below solution.

    We can also write radix-sort considering negative integers, just a little complicated.

    class Solution(object):
        def radixSort(self, nums):
            nums = map(str, nums)
            k = max(map(len, nums))
            nums = ['0' * (k - len(num)) + num for num in nums]
    
            for i in xrange(k - 1, -1, -1):
                buckets = [[] for _ in xrange(10)]
                for num in nums:
                    buckets[ord(num[i]) - 48].append(num)
                nums = sum(buckets, [])
            return map(int, nums)
    
        def wiggleSort(self, nums):
            sortNums, n = self.radixSort(nums), len(nums) | 1
            for i, num in enumerate(sortNums[::-1]):
                nums[(2*i + 1) % n] = num

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.