LeetCode 排序章节

仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。

示例 1：

输入：stock = [2,5,7,4], cnt = 1
输出：[2]

示例 2：

输入：stock = [0,2,3,6], cnt = 2
输出：[0,2] 或 [2,0]

提示：

• 0 <= cnt <= stock.length <= 10000
• 0 <= stock[i] <= 10000

借助快排的思想划分出小于cnt的区间即可。

vector<int> inventoryManagement(vector<int>& stock, int cnt) {if (cnt == 0)return {};srand(time(nullptr));qsortK(stock, 0, stock.size() - 1, cnt);return {stock.begin(), stock.begin() + cnt};
}// 借助快排思想，以k划分数组
void qsortK(vector<int>& stock, int left, int right, int k) {if (left == right)return;int key = stock[rand() % (right - left + 1) + left];int i = left, l = left, r = right;while (i <= r) {if (stock[i] < key)swap(stock[l++], stock[i++]);else if (stock[i] > key)swap(stock[r--], stock[i]);elsei++;}// [left, l - 1] [l, r] [r + 1, right]if (k <= l - left)qsortK(stock, left, l - 1, k);else if (k <= r - left + 1)return;elseqsortK(stock, r + 1, right, k - (r - left + 1));return;
}

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

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

示例 2：

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

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

遍历数组，保持[0, left - 1]全为0，[right + 1, nums.size() - 1]全为2，最后[left, right]就全为1了。当i > right，就完成了数组划分，不用再继续遍历了。三种情况，对应操作：

• nums[i] == 0时，交换nums[left]与当前值并i++。
• nums[i] == 1时，i++即可。
• nums[i] == 2时，交换nums[left]，但不能i++，还要对交换得到值再进行判断。

void sortColors(vector<int>& nums) {int left = 0, right = nums.size() - 1;int i = 0;while (i <= right) {if (nums[i] == 0)swap(nums[left++], nums[i++]);else if (nums[i] == 1)i++;else // nums[i] == 2swap(nums[right--], nums[i]);}
}

给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= 5 * 10^4
• -5 * 10^4 <= nums[i] <= 5 * 10^4

根据rand()随机生成的值作为下标找到key，借助75. 颜色分类的思想以key将数组分为三个部分，nums[i] < key，nums[i] == key，nums[i] > key，不断递归即可实现快速排序。

将数组划分为三块而不是两块，避免数组全部相同时，快排时间复制度过高。

vector<int> sortArray(vector<int>& nums) {srand(time(nullptr));qsort(nums, 0, nums.size() - 1);return nums;
}void qsort(vector<int>& nums, int left, int right) {if (left >= right) return;// 随机获取keyint key = nums[rand() % (right - left + 1) + left];// 数组划分为三块int i = left, l = left, r = right;while (i <= r) {if (nums[i] < key)swap(nums[l++], nums[i++]);else if (nums[i] > key)swap(nums[r--], nums[i]);else i++;}// [left, l - 1] [l, r] [r + 1, right]qsort(nums, left, l - 1);qsort(nums, r + 1, right);
}

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

借助快速排序的思想解决topK问题，快速选择将数组划分为三块，对应三种情况进行查找，不断递归即可：

[left, l - 1] [l, r] [r + 1, right]

• 当k小于等于右区间的长度，既k <= right - r时，继续在右区间查找第k大的数。
• 当k小于等于右区间＋中间相同字符的长度，既k <= right - l + 1时，第k大的数就在中间区间为key。
• 当k大于右区间＋中间相同字符的长度时，既k在左区间时，在左区间查找第k大的数减去右区间＋中间相同字符的长度，既第k - (right - l + 1)大的数。

int findKthLargest(vector<int>& nums, int k) {srand(time(nullptr));int left = 0, right = nums.size() - 1;return topK(nums, left, right, k);
}int topK(vector<int>& nums, int left, int right, int k) {if (left == right)return nums[left];// 随机获取keyint key = nums[rand() % (right - left + 1) + left];// 数组划分为三块int i = left, l = left, r = right;while (i <= r) {if (nums[i] < key)swap(nums[l++], nums[i++]);else if (nums[i] > key)swap(nums[r--], nums[i]);elsei++;}// [left, l - 1] [l, r] [r + 1, right]if (k <= right - r)return topK(nums, r + 1, right, k);else if (k <= right - l + 1)return key;elsereturn topK(nums, left, l - 1, k - (right - l + 1));
}

给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= 5 * 10^4
• -5 * 10^4 <= nums[i] <= 5 * 10^4

vector<int> tmp; // 避免重复创建vectorvector<int> sortArray(vector<int>& nums) {tmp.resize(nums.size());mergeSort(nums, 0, nums.size() - 1);return nums;
}void mergeSort(vector<int>& nums, int left, int right) {if (left >= right)return;int mid = (right + left) / 2;mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);// 合并两个有序数组int pos = left;int cur1 = left, cur2 = mid + 1;while (cur1 <= mid && cur2 <= right)tmp[pos++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];while (cur1 <= mid)tmp[pos++] = nums[cur1++];while (cur2 <= right)tmp[pos++] = nums[cur2++];for (int i = left; i <= right; ++i)nums[i] = tmp[i];
}

给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例 1：

输入：nums = [5,2,6,1]
输出：[2,1,1,0] 
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

示例 2：

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

示例 3：

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

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

在合并过程中，利用双指针 cur1和cur2分别遍历左右子数组：

• 若 nums[cur1] <= nums[cur2]，表明当前 cur2 对应的元素更大，把 cur2 相关信息存入临时数组。
• 若 nums[cur1] > nums[cur2]，意味着 cur1 对应的元素大于右半区间从 cur2 到 right 的所有元素，所以 counts[index[cur1]] 增加 right - cur2 + 1，并将 cur1 相关信息存入临时数组。

和这题LCR 170. 交易逆序对的总数类似，不同之处在于，本题需要数组中每个元素右侧小于该元素的元素数量保存在新数组中对应位置中。由于归并排序会重新排列数组元素，排序时，无法得知各元素在原数组中对应的位置。如何若使用哈希表记录，无法处理重复元素的情况。因此，我们引入一个 index 数组，让它随着元素数组同步移动。通过 index 数组，我们可以依据元素在当前数组中的位置，对应到其在原数组中的下标。

vector<int> tmp_nums;
vector<int> index;
vector<int> tmp_index;
vector<int> counts;vector<int> countSmaller(vector<int>& nums) {int n = nums.size();tmp_nums.resize(n);index.resize(n);for (int i = 0; i < n; ++i)index[i] = i;tmp_index.resize(n);counts.resize(n);mergeSort(nums, 0, n - 1);return counts;
}void mergeSort(vector<int>& nums, int left, int right) {if (left >= right)return;int mid = (right + left) / 2;mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);// 合并两个有序数组int pos = left;int cur1 = left, cur2 = mid + 1;while (cur1 <= mid && cur2 <= right) {if (nums[cur1] <= nums[cur2]) {tmp_index[pos] = index[cur2];tmp_nums[pos++] = nums[cur2++];} else {counts[index[cur1]] += right - cur2 + 1;tmp_index[pos] = index[cur1];tmp_nums[pos++] = nums[cur1++];}}while (cur1 <= mid) {tmp_index[pos] = index[cur1];tmp_nums[pos++] = nums[cur1++];}while (cur2 <= right) {tmp_index[pos] = index[cur2];tmp_nums[pos++] = nums[cur2++];}for (int i = left; i <= right; ++i) {index[i] = tmp_index[i];nums[i] = tmp_nums[i];}
}

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个*重要翻转对*。

你需要返回给定数组中的重要翻转对的数量。

示例 1:

输入: [1,3,2,3,1]
输出: 2

示例 2:

输入: [2,4,3,5,1]
输出: 3

注意:

1. 给定数组的长度不会超过50000。
2. 输入数组中的所有数字都在32位整数的表示范围内。

统计满足nums[i] > 2 * nums[j]的数对数量，使用双指针 cur1 和 cur2 分别遍历左右两部分：

• 当 (long long)nums[cur1] <= 2 * (long long)nums[cur2] 时，将 cur1 指针后移。
• 当 (long long)nums[cur1] > 2 * (long long)nums[cur2] 时，说明 nums[cur1] 到 nums[mid] 的所有元素都满足条件，将 ans 增加 mid - cur1 + 1，并将 cur2 指针后移。

int ans = 0;
vector<int> tmp;
vector<long long> nums2;int reversePairs(vector<int>& nums) {int n = nums.size();tmp.resize(n);nums2.resize(n);mergeSort(nums, 0, n - 1);return ans;
}void mergeSort(vector<int>& nums, int left, int right) {if (left >= right)return;int mid = (right + left) / 2;mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);// 模拟左边的原数组与右边的二倍数组合并过程，求ansint pos = left;int cur1 = left, cur2 = mid + 1;for (int i = cur2; i <= right; ++i)nums2[i] = (long long)2 * nums[i];while (cur1 <= mid && cur2 <= right) {if (nums[cur1] <= nums2[cur2]) {pos++;cur1++;} else {ans += mid - cur1 + 1;pos++;cur2++;}}// 原数组合并pos = left;cur1 = left, cur2 = mid + 1;while (cur1 <= mid && cur2 <= right) {if (nums[cur1] <= nums[cur2])tmp[pos++] = nums[cur1++];elsetmp[pos++] = nums[cur2++];}while (cur1 <= mid)tmp[pos++] = nums[cur1++];while (cur2 <= right)tmp[pos++] = nums[cur2++];for (int i = left; i <= right; ++i)nums[i] = tmp[i];
}

在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。

示例 1：

输入：record = [9, 7, 5, 4, 6]
输出：8
解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。

提示：

0 <= record.length <= 50000

在合并数组的过程中，当发现左子数组的当前元素大于右子数组的当前元素时，将右子数组元素放入辅助数组，和统计逆序对的数量所需的基本框架相同。

• 如果 record[cur1] <= record[cur2]，说明没有形成逆序对，将 record[cur1] 放入 tmp 数组，并将 cur1 指针后移。
• 如果 record[cur1] > record[cur2]，说明形成了逆序对，由于左半部分是有序的，那么 record[cur1] 到 record[mid] 的所有元素都与 record[cur2] 构成逆序对，逆序对的数量增加 mid - cur1 + 1，将 record[cur2] 放入 tmp 数组，并将 cur2 指针后移。

int ans = 0; 
vector<int> tmp;int reversePairs(vector<int>& record) {tmp.resize(record.size());mergeSort(record, 0, record.size() - 1);return ans;
}void mergeSort(vector<int>& record, int left, int right) {if (left >= right)return;int mid = (right + left) / 2;mergeSort(record, left, mid);mergeSort(record, mid + 1, right);// 合并两个有序数组int pos = left;int cur1 = left, cur2 = mid + 1;while (cur1 <= mid && cur2 <= right) {if (record[cur1] <= record[cur2]) {tmp[pos++] = record[cur1++];} else {ans += mid - cur1 + 1;tmp[pos++] = record[cur2++];}}while (cur1 <= mid)tmp[pos++] = record[cur1++];while (cur2 <= right)tmp[pos++] = record[cur2++];for (int i = left; i <= right; ++i)record[i] = tmp[i];
}