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

Leetcode 每日一题——164. 最大间距

程序员文章站 2022-04-04 10:01:23
...

164. 最大间距

给定一个无序的数组,找出数组在排序之后,相邻元素之间最大的差值。

如果数组元素个数小于 2,则返回 0。

Leetcode 每日一题——164. 最大间距
该题目最麻烦的是要在线性复杂度下解决问题,所以可以使用基数排序的方法(虽然评论区都说效果一般),下面是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

运行效果:
Leetcode 每日一题——164. 最大间距
用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 每日一题——164. 最大间距

来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/maximum-gap