（力扣164）C语言-基数排序最大间距

2024/10/26 5:17:53 来源：https://blog.csdn.net/qq_65265649/article/details/141617278 浏览: 次关键词：（力扣164）C语言-基数排序最大间距

文章目录

题目
解题思路
代码

题目来源力扣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 <= 105
0 <= nums[i] <= 109

解题思路

基数排序的主要思想
遍历数组元素，按每个数组元素的各位、十位、百位等进行分配，再按序收集。

分配不难，主要是如何收集，其实我一开始接触到基数排序是在数据结构中，当时用的是链表，不过没有具体代码，只是简单了解一下思想，本题是具体实现，但是用的是数组。
收集的时候有个注意事项：用数组收集是我们是反向遍历数据的，但用链表实现时，正向遍历数组。
因为收集是按照先进先出（队列）的原则的，数组正向遍历是后进先出（栈），所以我们要反向遍历数组进行收集。

思路大致如下。我会在左边写出数组的分配形式，右边配有链表的思路，便于大家理解。
在这里插入图片描述

在这里插入图片描述

代码注释也写了一些我做题时的想法

代码

int maximumGap(int* nums, int numsSize) {if (numsSize == 1) {return 0;}int exp = 1;//个位，十位，百位…int buf[numsSize];memset(buf, 0, sizeof(buf));int maxVal = INT_MIN;for (int i = 0; i < numsSize; i++) {maxVal = fmax(maxVal, nums[i]);//找最大值干嘛呢？//为了确定我们要进行几次分配收集}while (maxVal >= exp) {int cnt[10];//0-9,余数memset(cnt, 0, sizeof(cnt));for (int i = 0; i < numsSize; i++) {int digit = (nums[i] / exp) % 10;cnt[digit]++;//统计余数为i的有多少个元素}for (int i = 1; i < 10; i++) {cnt[i] += cnt[i - 1];//这一步是干嘛？//好像大概懂了，统计到i为止共有多少个元素，方便后面的排序}for (int i = numsSize - 1; i >= 0; i--) {int digit = (nums[i] / exp) % 10;buf[cnt[digit] - 1] = nums[i];//收集cnt[digit]--;}memcpy(nums, buf, sizeof(int) * numsSize);//在排序了exp *= 10;}int ret = 0;for (int i = 1; i < numsSize; i++) {ret = fmax(ret, nums[i] - nums[i - 1]);}return ret;
}