164. Maximum Gap

yPhantom 2019年10月14日 29次浏览

2019-9-24

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Return 0 if the array contains less than 2 elements.

Example 1:

Input: [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either
             (3,6) or (6,9) has the maximum difference 3.

Example 2:

Input: [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.

Note:

  • You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
  • Try to solve it in linear time/space.

Solution

给一个未排序的数组,让找到排序后数组中相邻数字间最大的差值。要求O(n)的时间与O(n)的空间复杂度。

先给出python3的解法吧:

import math

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        nums_len = len(nums)
        if nums_len < 2:
            return 0
        max_value = max(nums)
        min_value = min(nums)
        
        average_gap = math.ceil((max_value - min_value) / (nums_len - 1))

        min_array = [max_value] * (nums_len - 1)
        max_array = [min_value] * (nums_len - 1)
        
        for num in nums:
            if num == max_value or nums == min_value:
                continue
            index = (num - min_value) // average_gap
            min_array[index] = min(min_array[index], num)
            max_array[index] = max(max_array[index], num)

        max_gap = float('-inf')
        previous = min_value
        for i in range(nums_len - 1):
            if min_array[i] == max_value or max_array[i] == min_value:
                continue
            max_gap = max(max_gap, min_array[i] - previous)
            previous = max_array[i]
        
        max_gap = max(max_gap, max_value - previous)
        return max_gap

解法由评论区的一个Java版本改造而来。核心思想就是桶排序。