Leetcode 每日一题——164. 最大间距
程序员文章站
2022-04-04 10:01:23
...
164. 最大间距
给定一个无序的数组,找出数组在排序之后,相邻元素之间最大的差值。
如果数组元素个数小于 2,则返回 0。
该题目最麻烦的是要在线性复杂度下解决问题,所以可以使用基数排序的方法(虽然评论区都说效果一般),下面是Python的实现代码:
class Solution:
def maximumGap(self, nums: List[int]) -> int:
if len(nums) < 2: return 0
maxNum=max(nums)
exp=1
while(exp <= maxNum):
cont=dict()
for i in range(10):
cont[i]=list()
for i in nums:
index=int(i / exp) % 10
cont[index].append(i)
nums=[]
for i in range(10):
if len(cont[i]):
nums.extend(cont[i])
exp=10*exp
result=0
for i in range(1,len(nums)):
result=max(result,abs(nums[i]-nums[i-1]))
return result
运行效果:
用C++直接调用sort函数的代码如下:
class Solution {
public:
int maximumGap(vector<int>& nums) {
if (nums.size()<2) return 0;
sort(nums.begin(),nums.end());
int result=0;
for (int i=1;i<nums.size();++i)
{
result=max(result,nums[i]-nums[i-1]);
}
return result;
}
};
运行效果(也没有太差O(∩_∩)O哈哈~):
来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/maximum-gap