Maximum Gap

题目描述

解题方法

naive的方法，先sort

没想法就先跟面试官说sort,让他知道你是有办法做出来的，但是sort的时间复杂度是O(nlogn)

bucket sort

O(nlogn)的方法无法满足我们，那我们就应该想o(n)，甚至o(logn)的方法。

能够达到O(n)的sort的方法有

• bucket sort
• counting sort
• radix sort

这里我们可以用Bucket sort的方法，找出最大值和最小值确定范围，然后有n个数，最小的gap也就是平均分就是(max-min) / (n-1)， 所以我们可以有n个bucket。在同一个bucket内的数肯定不会是最大gap，应该找两个相邻的Bucket里的前面的最大值和后面bucket的最小值的gap, 有可能是结果。

Solution

sort的方法

class Solution(object):
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        if length < 2:
            return 0
        nums.sort()

        maxGap = 0
        for i in range(1, length):
            gap = nums[i] - nums[i-1]
            if gap > maxGap:
                maxGap = gap

        return maxGap

bucket sort

class Solution(object):
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        if length < 2:
            return 0

        minValue = sys.maxint
        maxValue = -sys.maxint
        for num in nums:
            if num > maxValue:
                maxValue = num
            if num < minValue:
                minValue = num

        bucketsNum = length + 1 # 有length + 1个bucket
        buckets = [[] for i in range(bucketsNum)]
        bucketSize = (maxValue - minValue) / bucketsNum + 1 # bucket的size也向上取整
        for num in nums:
            index = (num - minValue) / bucketSize # 注意要减去minValue
            buckets[index].append(num)

        p = 0
        maxGap = 0
        while p < bucketsNum:
            if not buckets[p]:
                p += 1
            nextP = p + 1
            while nextP < bucketsNum and not buckets[nextP]:
                nextP += 1
            if nextP >= bucketsNum:
                break
            gap = min(buckets[nextP]) - max(buckets[p])
            if gap > maxGap:
                maxGap = gap
            p = nextP

        return maxGap

Reference