LeetCode 164. Maximum Gap
Description
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.
描述
给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0。
示例 1:
输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
示例 2:
输入: [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。
说明:
你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。
请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。
思路
- 此题目使用桶排序.
- 我们首先获取数组的最小值mixnum和最大值maxnum，得到数组的范围.
- n个数有n-1个间隔，我们计算平均间隔gap：(maxnum-minnum)/n-1 向上取整.
- 我们计算需要的桶的个数size = int((maxnum-minnum)/gap)+1个
- 此题目的关键思想是：在一个桶内的数字之间的差值一定小于gap，如果某两个数之间的差大于平均差gap，一定会被放到两个桶内。最大的差一定大于等于gap（对一组数求平均值，平均值小于等于最大值），于是如果出现了两个数a，b，且a和b的差大于gap，那么a和b一定会被放到两个连续的桶t1，t2内，且a是t1桶的嘴后一个值（最大值），b是t2桶的第一个值（最小值）。于是我们只需要记录每个桶内的最大值和最小值，让后用当前桶内的最小值减去上一个桶内的最大值得到maxgap，取maxgap最大的一个返回即可.
- 要注意的是，如果在计算平均距离gap时候如果得到了0，说明所有的数相等，这时可以直接返回0.
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2019-01-16 12:08:24
# @Last Modified by: 何睿
# @Last Modified time: 2019-01-16 14:05:34
import math
import sys
class Solution(object):
def maximumGap(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# 获取数字的个数
count = len(nums)
# 如果小于两个数字，则根据题意返回0
if count < 2:
return 0
# 确定所有数的范围，寻找最值和最小值
maxnum, minnum = max(nums), min(nums)
# 计算数与数之间的平均距离（例如有10个数字，则一共有9个区间，平均的区间差为（最大值-最小值/9）向上取整）
gap = math.ceil((maxnum - minnum) / (count - 1))
# 如果gap等于0，说明所有的数值相等，直接返回0
if gap == 0:
return 0
# 计算需要多少个桶，桶个数为数组的返回/平均区间的范围+1
size = int((maxnum - minnum) / gap) + 1
# 存储每个桶的最小值，最大值
bucketmin, bucketmax = [sys.maxsize] * size, [-sys.maxsize] * size
for i in range(count):
# 计算当前值应该放到哪个桶内
index = int((nums[i] - minnum) / gap)
# 放最小值
bucketmin[index] = min(bucketmin[index], nums[i])
# 放最大值
bucketmax[index] = max(bucketmax[index], nums[i])
premax, maxgap = bucketmax[0], 0
# 最大的差值为当前桶的最小值减去前一个桶的最大值
for i in range(1, size):
if bucketmin[i] != sys.maxsize:
maxgap = max(maxgap, bucketmin[i] - premax)
premax = bucketmax[i]
return maxgap
