欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

困难难度-————(每日一题)LeetCode:164. 最大间距!!!!

程序员文章站 2022-04-04 10:06:00
...

题目:
164. 最大间距
给定一个无序的数组,找出数组在排序之后,相邻元素之间最大的差值。
如果数组元素个数小于 2,则返回 0。

示例 1:
输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6)(6,9) 之间都存在最大差值 3
示例 2:
输入: [10]
输出: 0
解释: 数组元素个数小于 2,因此返回 0
说明:
你可以假设数组中所有元素都是非负整数,且数值在 32 位有符号整数范围内。
请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。

解题思路1:
先把数组进行排序,然后遍历数组中的元素,找出相差最大的值,然后输出。
Code:

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        max = 0
        if len(nums) < 2:
            return 0
        nums.sort()           #将原来的数组进行排序
        for i in range(1,len(nums)):    #遍历数组中的元素
            l = nums[i] - nums[i-1]     #求相邻元素之间的差值
            if l > max:      #通过判断求出最大的差值
                max = l       
        return max          

运行结果:
困难难度-————(每日一题)LeetCode:164. 最大间距!!!!
解题思路2:
上面的sort排序是可以的,但是面试的时候这种解法肯定不能让面试官满意的。
所以我们可以理解成桶排序的问题。
1.我们期望将数组中的各个数等距离分配,也就是每个桶的长度相同,也就是对于所有桶来说,桶内最大值减去桶内最小值都是一样的。
困难难度-————(每日一题)LeetCode:164. 最大间距!!!!
可以当成公式来记。
2.确定桶的数量,最后的加一保证了数组的最大值也能分到一个桶。
困难难度-————(每日一题)LeetCode:164. 最大间距!!!!
3.我们的做法是要将数组中的数放到一个个桶里面,不断更新更大的(后一个桶内元素的最小值 - 前一个桶内元素的最大值),最后就得到了答案。
4.如何确定每个数应该对应哪个桶?
困难难度-————(每日一题)LeetCode:164. 最大间距!!!!
Code:

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        if not nums or len(nums) < 2: 
        	return 0
        
        max_ = max(nums)
        min_ = min(nums)
        max_gap = 0
        
        each_bucket_len = max(1,(max_-min_) // (len(nums)-1))   #求出每个桶的长度
        buckets =[[] for _ in range((max_-min_) // each_bucket_len + 1)]  #求出桶的数量
        
        for i in range(len(nums)):
            loc = (nums[i] - min_) // each_bucket_len
            buckets[loc].append(nums[i])
        
        prev_max = float('inf')
        for i in range(len(buckets)):
            if buckets[i] and prev_max != float('inf'):
                max_gap = max(max_gap, min(buckets[i])-prev_max)
            
            if buckets[i]:
                prev_max = max(buckets[i])
                
        return max_gap

运行结果:
困难难度-————(每日一题)LeetCode:164. 最大间距!!!!