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.
描述
給定一個無序的數(shù)組躁锡，找出數(shù)組在排序之后抒抬，相鄰元素之間最大的差值。
如果數(shù)組元素個數(shù)小于 2冲簿，則返回 0粟判。
示例 1:
輸入: [3,6,9,1]
輸出: 3
解釋: 排序后的數(shù)組是 [1,3,6,9], 其中相鄰元素 (3,6) 和 (6,9) 之間都存在最大差值 3。
示例 2:
輸入: [10]
輸出: 0
解釋: 數(shù)組元素個數(shù)小于 2峦剔，因此返回 0浮入。
說明:
你可以假設數(shù)組中所有元素都是非負整數(shù)，且數(shù)值在 32 位有符號整數(shù)范圍內羊异。
請嘗試在線性時間復雜度和空間復雜度的條件下解決此問題事秀。
思路
- 此題目使用桶排序.
- 我們首先獲取數(shù)組的最小值mixnum和最大值maxnum，得到數(shù)組的范圍.
- n個數(shù)有n-1個間隔野舶，我們計算平均間隔gap：(maxnum-minnum)/n-1 向上取整.
- 我們計算需要的桶的個數(shù)size = int((maxnum-minnum)/gap)+1個
- 此題目的關鍵思想是：在一個桶內的數(shù)字之間的差值一定小于gap易迹，如果某兩個數(shù)之間的差大于平均差gap，一定會被放到兩個桶內平道。最大的差一定大于等于gap（對一組數(shù)求平均值睹欲，平均值小于等于最大值），于是如果出現(xiàn)了兩個數(shù)a，b窘疮，且a和b的差大于gap袋哼，那么a和b一定會被放到兩個連續(xù)的桶t1，t2內闸衫，且a是t1桶的嘴后一個值（最大值）涛贯，b是t2桶的第一個值（最小值）。于是我們只需要記錄每個桶內的最大值和最小值蔚出，讓后用當前桶內的最小值減去上一個桶內的最大值得到maxgap弟翘，取maxgap最大的一個返回即可.
- 要注意的是，如果在計算平均距離gap時候如果得到了0骄酗，說明所有的數(shù)相等稀余，這時可以直接返回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
"""
# 獲取數(shù)字的個數(shù)
count = len(nums)
# 如果小于兩個數(shù)字，則根據(jù)題意返回0
if count < 2:
return 0
# 確定所有數(shù)的范圍趋翻，尋找最值和最小值
maxnum, minnum = max(nums), min(nums)
# 計算數(shù)與數(shù)之間的平均距離（例如有10個數(shù)字睛琳，則一共有9個區(qū)間，平均的區(qū)間差為（最大值-最小值/9）向上取整）
gap = math.ceil((maxnum - minnum) / (count - 1))
# 如果gap等于0踏烙，說明所有的數(shù)值相等师骗，直接返回0
if gap == 0:
return 0
# 計算需要多少個桶，桶個數(shù)為數(shù)組的返回/平均區(qū)間的范圍+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
