Concise Radix sort solution in python


  • 1
    A

    #Idea: Radix sort, using buckets to store all intermediate numbers
    #Time: O(10N) because 2^32 has ten digits, Space O(N)
    class Solution(object):
    def maximumGap(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if len(nums) < 2:
    return 0
    buckets = [[] for _ in range(10)]
    maxi = max(nums)
    i = 1 # i = 1, 10, 100, 1000....
    while maxi // i > 0:
    for num in nums:
    digit = (num // i) % 10
    buckets[digit].append(num)
    nums = [num for bucket in buckets for num in bucket]
    buckets = [[] for _ in range(10)]
    i *= 10
    max_gap = 0
    i = 0
    while i < len(nums) - 1:
    max_gap = max(max_gap,nums[i+1]-nums[i])
    i += 1
    return max_gap


Log in to reply
 

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