leetcode.164

LeetCode 164.最大间距

1 题目描述

• 题目链接：164.最大间距

给定一个无序的数组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 <= 10^5
• 0 <= nums[i] <= 10^9

2 思路

由于题目中要求必须要线性时间，且使用线性空间，因而不能采用传统的排序(快排的时间复杂度为nlogn)，我们可以用基数排序的方法，其时间复杂度和空间复杂度均为线性的。

//基数排序
void radixSort(int *nums, int numsSize, int exp){
    int buf[numsSize], bucket[10] = {0};
    for(int i = 0; i < numsSize; i++){
        bucket[(nums[i]/exp)%10] += 1;              //将每个nums放到对应的桶中
    }
    for(int i = 1; i < 10; i++){
        bucket[i] += bucket[i-1];                   //前缀和，确定每个nums的先后顺序
    }
    for(int i = numsSize - 1; i >= 0; i--){
        buf[bucket[(nums[i]/exp)%10]-1] = nums[i];  //将nums从桶中取出并暂存到buf数组中
        bucket[(nums[i]/exp)%10] -= 1;
    }
    for(int i = 0; i < numsSize; i++){
        nums[i] = buf[i];                           //将排序结果返回至原数组
    }
}

int maximumGap(int* nums, int numsSize){
    int max = INT_MIN;
    for(int i = 0; i < numsSize; i++){
        max = fmax(max, nums[i]);   //找最大元素以确定需要进行多少次排序操作
    }
    int exp = 1;                    //先对个位进行排序
    while(max >= exp){              //逐位进行基数排列
        radixSort(nums, numsSize, exp);
        exp *= 10;                  //切换操作位，个位、十位、千位...
    }
    int ans = 0;
    for(int i = 1; i < numsSize; i++){
        ans = fmax(ans, nums[i] - nums[i-1]);
    }
    return ans;
}