东莞网站建设电镀挂具,上海搬家公司电话附近,敦煌手机网站设计,长沙百度网站建设LeetCode-164. 最大间距【数组 桶排序 基数排序 排序】 题目描述#xff1a;解题思路一#xff1a;桶排序#xff0c;这种方法比较简单#xff0c;记住3个公式即可。如下#xff1a;解题思路二#xff1a;基数排序#xff0c;其实和桶排序差不多#xff0c;就是直接分为… LeetCode-164. 最大间距【数组 桶排序 基数排序 排序】 题目描述解题思路一桶排序这种方法比较简单记住3个公式即可。如下解题思路二基数排序其实和桶排序差不多就是直接分为十个桶(0-9十位刚好十个桶)。然后按照个位,十位,百位...上面对应的数放入桶中进行排序。而基数排序可以在 O(N)的时间内完成整数之间的排序。解题思路三0 题目描述
给定一个无序的数组 nums返回 数组在排序之后相邻元素之间最大的差值 。如果数组元素个数小于 2则返回 0 。
您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。
示例 1: 输入: nums [3,6,9,1] 输出: 3 解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
示例 2: 输入: nums [10] 输出: 0 解释: 数组元素个数小于 2因此返回 0。
提示: 1 nums.length 105 0 nums[i] 109
解题思路一桶排序这种方法比较简单记住3个公式即可。如下
难度在于两个线性。
首先我们期望将数组中的各个数等距离分配也就是每个桶的长度相同也就是对于所有桶来说桶内最大值减去桶内最小值都是一样的。 每个桶的长度 max ( 1 , ⌊ max ( n u m s ) − min ( n u m s ) l e n ( n u m s ) − 1 ⌋ ) \max(1,\lfloor{{\max(nums) - \min(nums)} \over {len(nums) - 1}}\rfloor) max(1,⌊len(nums)−1max(nums)−min(nums)⌋)确定桶的数量最后的加一保证了数组的最大值也能分到一个桶。 桶的数量 ⌊ max ( n u m s ) − min ( n u m s ) 每个桶的长度 ⌋ 1 \lfloor{{\max(nums) - \min(nums)} \over {每个桶的长度}}\rfloor 1 ⌊每个桶的长度max(nums)−min(nums)⌋1确定每个数应该对应哪个桶 l o c a t i o n n u m s [ i ] − min ( n u m s ) 每个桶的长度 location {{nums[i] - \min(nums)} \over {每个桶的长度}} location每个桶的长度nums[i]−min(nums)
我们的做法是要将数组中的数放到一个个桶里面不断更新更大的后一个桶内元素的最小值 - 前一个桶内元素的最大值最后就得到了答案。
class Solution:def maximumGap(self, nums: List[int]) - int:if len(nums)2: return 0max_n max(nums)min_n min(nums)max_gap 0each_bucket_len max(1, (max_n-min_n) // (len(nums)-1))buckets [[] for _ in range((max_n-min_n) // each_bucket_len 1)]# 把数字放入桶中for i in range(len(nums)):loc (nums[i]-min_n) // each_bucket_lenbuckets[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时间复杂度O(n) 空间复杂度O(n) 例如 nums [1,3,4,5,6,10,11,12,17] 每个桶的长度 17 - 1 / (9-1) 2 桶的个数 17-1/ 2 1 9 所以我们的桶为左闭右开
区间[1,3)[3,5)[5,7)[7,9)[9,11)[11,13)[13,15)[15,17)[17,19)元素13,45,61011,1217
差值3-1 25-4 110-6 411-10 117-12 5答案 max差值 5
解题思路二基数排序其实和桶排序差不多就是直接分为十个桶(0-9十位刚好十个桶)。然后按照个位,十位,百位…上面对应的数放入桶中进行排序。而基数排序可以在 O(N)的时间内完成整数之间的排序。
class Solution:def maximumGap(self, nums: List[int]) - int:if len(nums)2: return 0 # 极端情况# 基数排序i 0 # 记录当前正在排拿一位最低位为1(10**i)max_n max(nums)j len(str(max_n))# 记录最大值的位数while i j:buckets [[] for _ in range(10)] # 0-9十位刚好十个桶for x in nums:buckets[int( x / (10**i)) % 10].append(x) # 将nums中对应每位放入相应的桶中nums.clear()for x in buckets: # 将按位排序好的桶中元素放回原数组for y in x:nums.append(y)i 1 # 进行下一位排序 个位 十位 百位...return max(nums[i]-nums[i-1] for i in range(1, len(nums)))
时间复杂度O(n) 空间复杂度O(n)
解题思路三0
