网络异常，图片无法展示
|
「这是我参与2022首次更文挑战的第14天，活动详情查看：2022首次更文挑战」
给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0。
示例 1:
输入: [3,6,9,1] 输出: 3 解释: 排序后的数组是 [1,3,6,9] , 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。 复制代码
示例 2:
输入: [10] 输出: 0 解释: 数组元素个数小于 2，因此返回 0。 复制代码
说明:
- 你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。
- 请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。
解题思路
本题给出了信息：
- 数组中所有元素都是非负整数
- 数值在 32 位有符号整数范围内
给出了要求：
- 在线性时间复杂度和空间复杂度的条件下解决此问题
因为本题要求的是数组排序之后的相邻元素之间的最大差值，所以我们要对输入数组进行排序。
而本题要求在线性时间复杂度和空间复杂度的条件下解决此问题，就说明我们算法的时间复杂度和空间复杂度都应该是 O(n) 的，而排序算法中时间复杂度为 O(n) 的我们可以想到 计数排序 和 基数排序。而这里题目给出的信息，数值是在 32 位有符号整数范围内，所以如果使用 计数排序，开的计数数组会很大，所以我们可以采用 基数排序 对输入数组进行排序，然后遍历排序后的结果，获取最大差值即可。
代码实现
// 获取低 16 位 function low16(num){ return num & 0xffff } // 获取高 16 位 function high16(num){ return (num & 0xffff0000) >> 16 } var maximumGap = function (nums) { // 获取输入数组长度 const len = nums.length; // 如果输入数组长度小于 2，直接返回 0 if(len<2) return 0; // 创建计数数组 const count = Array(65536).fill(0), // 创建 temp 数组存储低 16 位排序后的结果 temp = Array(len) // 低十六位排序 // 计数 for(let i = 0;i<len;i++) count[low16(nums[i])]++ // 求前缀和 for(let i = 1;i<65536;i++) count[i] += count[i-1] // 归位 for(let i = len-1;i>=0;i--) temp[--count[low16(nums[i])]] = nums[i] // 重置 count for (let i = 0; i < 65536; i++) count[i] = 0 // 高十六位排序 // 计数 for(let i = 0;i<len;i++) count[high16(temp[i])]++ // 求前缀和 for(let i = 1;i<65536;i++) count[i] += count[i-1] // 归位 for(let i = len-1;i>=0;i--) nums[--count[high16(temp[i])]] = temp[i] // 初始化结果值为 0 let res = 0 // 根据排序后的 nums 求最大间距 for (let i = 1; i < len; i++) res = Math.max(res, nums[i] - nums[i - 1]) // 返回结果值 return res } 复制代码
至此我们就完成了 leetcode-164-最大间距
如有任何问题或建议，欢迎留言讨论！👏🏻👏🏻👏🏻
