240427 leetcode exercises

240427 leetcode exercises

@jarringslee

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。

​ 如果把这道题拆开做——先排序，再求值，就会简单很多。

🔁排序遍历法

• 排序

  这里我们依旧优先选择快排。这里也可以尝试归并排序或者堆排序。感觉用冒泡会超时。

• 求值

​ 整型变量max储存当前记录下的量逐渐最大差值。然后for循环遍历即可求得数组中的最大差值

//快排
int cmp(const void* a, const void* b) {return (*(int*)a) - (*(int*)b);
}int maximumGap(int* nums, int numsSize) {int max = 0;if (numsSize < 2) {return 0;}qsort(nums, numsSize, sizeof(int), cmp);//循环取最大值for (int i = 0; i < numsSize - 1; i++) {if (nums[i + 1] - nums[i] > max){max = nums[i + 1] - nums[i]}}return max;
}

581. 最短无序连续子数组

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组，并输出它的长度。

示例 1：

输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

示例 2：

输入：nums = [1,2,3,4]
输出：0

示例 3：

输入：nums = [1]
输出：0

🔁排序定位法

​ 应该是最大众最直观的一个解法。题目要求返回第k个最大的数字，就是数组排序后的倒数第k个数字。

我们在这里依旧采用尊贵的快速排序。

随后便可以直接返回要找的第k大的数字。

int cmp(const void* a, const void *b){return (*(int*)a) - (*(int*)b);
}
int findKthLargest(int* nums, int numsSize, int k) {qsort (nums, numsSize, sizeof(int), cmp);return nums[numsSize - k];
}

但是题目只想让我们找到那个特定的数字，并没有要求我们进行排序。而且就找一个数字而把整个数组排序有没有可能有点多此一举了呢？

其实我们可以不进行排序，而是记录，通过某种方式记录下来之后再返回，肯定比排序的复杂度要低很多。

🔁计数扫描法

哈希。

题目中假设所有元素都在 −10000,10000-10000, 10000−10000,10000 范围内。我们用一个大小为 20001（或略大留余地）的整型数组 ash做“桶”，下标 i对应的桶里存储值i - OFFSET出现的次数。其中OFFSET = 10000，即元素 x对应桶索引x + OFFSET`。

第一次遍历：统计频次，记录最大值
遍历一遍原数组 nums，对于每个元素 x：

hash[x + OFFSET]++;      // 频次加 1
if (x > max) max = x;    // 顺便更新当前见过的最大值

这样我们既完成了“计数排序”的准备工作，还知道了数据中的最大元素，后续无需每次都从下标 20000 向前搜。

第二次扫描：反向累减找第 k 大
从最大值对应的桶开始向小的方向（桶下标依次减 1）走，用一个变量 remain = k：

int idx = max + OFFSET;    // 从这个桶开始往下走
while (remain > 0) {remain -= hash[idx];idx--;
}
// 当跳出循环时，idx 多走了一步，所以真实值是 (idx+1) - OFFSET
return idx + 1 - OFFSET;

每到一个桶，就把该桶内元素总数从 remain 中减去，直到 remain ≤ 0，此时对应的元素就是第 k 大。

int findKthLargest(int* nums, int numsSize, int k) {// 1. 准备：桶大小留出整块区间 [-10000,10000]const int OFFSET = 10000;const int BUCKETS = 20001;         // 下标 0…20000static int hash[BUCKETS];          // 这里用 static 避免栈溢出memset(hash, 0, sizeof(hash));     // 清零// 2. 遍历 nums，统计频次并记录最大值int max = -10001;                  // 初始化低于最小可能值for (int i = 0; i < numsSize; i++) {int x = nums[i];hash[x + OFFSET]++;if (x > max) {max = x;}}// 3. 从 max 开始往小方向扫描，找第 k 大int remain = k;int idx = max + OFFSET;while (remain > 0) {// 减去当前桶中所有元素remain -= hash[idx];idx--;}// 跳出时 idx 指向比答案小 1 的桶，下标 idx+1 才是答案return (idx + 1) - OFFSET;
}