Simple radix sort solution in python


  • 4
    X
    class Solution:
        # @param {integer[]} nums
        # @return {integer}
        def radixSort(self, A): 
            for k in xrange(10):     
                s=[[] for i in xrange(10)]
                for i in A:
                    s[i/(10**k)%10].append(i)
                A=[a for b in s for a in b] 
            return A
        
        def maximumGap(self, nums): 
            A = self.radixSort(nums)
            ans = 0
            if len(A) == 0: return 0
            prev = A[0]
            for i in A:
                if i - prev > ans: ans = i - prev
                prev = i
            return ans

  • 0
    M

    not in constant space right?


  • 0
    X

    linear space/time


  • 0
    A

    Similar idea and code

    class Solution(object):
        def maximumGap(self, nums):
            radix, maxg=1, 0
            for _ in range(10):
                bus=[[] for _ in range(10)]
                for n in nums:
                    bus[(n/radix)%10]+=n,
                nums=reduce(lambda x,y: x+y, bus)
                radix*=10
            for i, n in enumerate(nums[1:]):
                maxg=max(n-nums[i], maxg)
            return maxg

  • 0

    @AceSmg not very understandable code. Check this out:

    class Solution(object):
        def maximumGap(self, nums):
            def radixsort(nums):
                idx, bits = 0, 32
                while idx < bits:
                    zeroes, ones = [], []
                    for num in nums:
                        if num & (1 << idx): 
                            ones.append(num)
                        else: zeroes.append(num)
                    nums = zeroes + ones
                    idx += 1
                return nums
            
            nums = radixsort(nums)
            return max([b - a for a, b in zip(nums, nums[1:])] or [0])
    

  • 0
    C

    If I understand the problem description correctly (max(j - i) for all i, j fulfilling a[i] <= a[j]), the solution seems to be wrong to me.

    For example, chosing a = [4, 9, 2, 6, 8, 1] results in maximumGap(a) = 2. The right solution in this case would be 4 - 0 = 4, since a[4] = 8 < a[0] = 0.


Log in to reply
 

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