Did anyone try bucket sort?


  • 0
    T

    Although in some worse cases the time complexity is O(nlogn), in average it performs quite well.

    class Solution(object):
        def findKthLargest(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: int
            """
            if not nums: return
            minVal, maxVal = 2**31-1, -2**31
            for num in nums:
                if num < minVal: minVal = num
                if num > maxVal: maxVal = num
            buckets = [[]]*len(nums)
            size = (maxVal - minVal)/len(nums)+1
            for num in nums:
                buckets[(num - minVal)/size].append(num)
            cnt = 0
            for i in xrange(len(nums)-1,-1,-1):
                cnt += len(buckets[i])
                if cnt >= k: break
            buckets[i].sort()
            return buckets[i][cnt - k]
            
    

Log in to reply
 

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