Help! I use radix sort (python) correct in my IDE, but can not pass negative number case...


  • 0
    S
    class Solution:
    # @param num, a list of integer
    # @return an integer
    def longestConsecutive(self, num):
        sorted_num = self.radixsort(num)
        cont, longest = 0, 0
        if len(sorted_num) == 0 :
            return 0
        elif len(sorted_num) == 1 :
            return 1
        elif len(sorted_num) == 2 :
            if sorted_num[0] + 1 == sorted_num[1] :
                return 2
            else:
                return 1
        for i in range(1,len(sorted_num)-1):
            if sorted_num[i] == sorted_num[i+1]-1 and sorted_num[i] == sorted_num[i-1]+1:
                cont += 1
            else:
                cont = 0
            longest = max(longest, cont)
        return longest + 2
        
    def radixsort(self, num):
        RADIX = 10
        maxLength = False
        tmp , placement = -1, 1
    
        while not maxLength:
            maxLength = True
            # declare and initialize buckets
            buckets = [list() for _ in range( RADIX )]
    
            # split aList between lists
            for i in num:
                tmp = i / placement
                buckets[tmp % RADIX].append( i )
                if maxLength and tmp > 0:
                    maxLength = False
                #print buckets
            # empty lists into aList array
            a = 0
            for b in range( RADIX ):
                buck = buckets[b]
                for i in buck:
                    num[a] = i
                    #print aList
                    a += 1
            # move to next digit
            placement *= RADIX
        return num

  • 1
    D

    You need to take note that in python:
    (-1) % 10 = 9, and
    1 % 10 = 1

    Hence, you need to tweak your algorithm a little bit. The idea is to put the negative numbers to bins from 1 to 9 while put non-negative numbers from 9 to 18;

    Below is the sample code for radix sort:

    def radixSort(a):
        r = 10
        maxLen = 11
        for x in range(maxLen):
            bins = [[] for i in range(r+9)]
            for y in a:
                if(y>=0):
                    bins[(y/10**x)%r+9].append(y)
                else:
                    bins[(y/10**x)%r].append(y)
            a=[]
            for section in bins:
                a.extend(section)
        return a

Log in to reply
 

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