Radix sort solution in Go


  • 0
    N
    func sortByBit(nums []int, b uint) []int {
    	var buckets [2]int
    	for _, num := range nums {
    		if num&(1<<b) == 0 {
    			buckets[1]++
    		}
    	}
    
    	result := make([]int, len(nums))
    	for _, num := range nums {
    		if num&(1<<b) == 0 {
    			result[buckets[0]] = num
    			buckets[0]++
    		} else {
    			result[buckets[1]] = num
    			buckets[1]++
    		}
    	}
    	return result
    }
    
    func radixSort(nums []int) []int {
    	for i := uint(0); i < 31; i++ {
    		nums = sortByBit(nums, i)
    	}
    	return nums
    }
    
    func maximumGap(nums []int) int {
    	if len(nums) < 2 {
    		return 0
    	}
    
    	sortedNums := radixSort(nums)
    	maxDiff := 0
    	for i := 0; i < len(sortedNums)-1; i++ {
    		diff := sortedNums[i+1] - sortedNums[i]
    		if diff > maxDiff {
    			maxDiff = diff
    		}
    	}
    
    	return maxDiff
    }
    

Log in to reply
 

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