1. 颜色分类

1.1 题目来源

75. 颜色分类

1.2 题目描述

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

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

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

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

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

1.3 题目解析

方法一：使用快速排序

这里就是简单的一个快排模板了.

class Solution {
public:void QuickSortHoare(vector<int>& a, int left, int right){if (left >= right)return;int l = left, r = right;int key = left;while (l < r){while (l < r && a[r] >= a[key]) // 这里要注意了一定要写等号,也必须是r先--在l++r--;while (l < r && a[l] <= a[key])l++;swap(a[l], a[r]);}swap(a[left], a[l]);QuickSortHoare(a, left, l - 1);QuickSortHoare(a, l + 1, right);}void sortColors(vector<int>& nums) {QuickSortHoare(nums, 0, nums.size() - 1);}
};

方法二：三指针

我们可以将整个数组分成三部分呢，第一部分全部是0，第二部分全部都是1，第三部分全部都是2。于是我们可以定义三个指针，left，cur，right，left代表第一部分的最右边，right代表第三部分的最左边，cur指针用于遍历整个数组。这样的话我们就可以得到一个范围，即[left,l]为第一部分，[l + 1, r - 1]是第二部分，[r, right]是第三部分。

这里的解题思路可以参考移动零。

所以我们就可以得到三个部分：

1. 如果nums[cur] == 0 ，就swap（nums[cur], nums[left + 1]，同时将left和cur都进行++
2. 如果nums[cur] == 1，则cur直接进行++
3. 如果num[cur] == 2，则swap(nums[cur], nums[right - 1])，同时right进行–，这个时候cur不需要进行++，因为right - 1下标对应的数据是还没有进行判断的，有可能是0，有可能是1，也有可能是2，是不确定的，所以还需要进行判断。

class Solution {
public:void sortColors(vector<int>& nums) {int n = nums.size();int left = -1 , right = n;int cur = 0;while (cur < right){if (nums[cur] == 0){swap(nums[left + 1], nums[cur]);left++;cur++;}else if (nums[cur] == 1){cur++;}else{swap(nums[right - 1],nums[cur]);right--;}}}
};

2. 排序数组

2.1 题目来源

912. 排序数组

2.2 题目描述

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

1. 示例 1：
   输入：nums = [5,2,3,1]
   输出：[1,2,3,5]
2. 示例 2：
   输入：nums = [5,1,1,2,0,0]
   输出：[0,0,1,1,2,5]

提示：
1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104

2.3 题目解析

方法一：快排模板

直接使用快排模板，这里需要注意了int key = a[(left + right) >> 1];必须写成key直接拿到值，不能使用通过拿到下标的方式int key = (left + right) >> 1，然后后序使用while (a[r] > a[key])这样通过索引的方式进行判断，因为可能在整个whiel(l < r）的阶段中key所对应下标的值会发生改变。只有一开始拿到索引对应的值后继续使用方可。

class Solution {
public:void _sort(vector<int>& a, int left, int right){if (left >= right) return;int l = left, r = right;int key = a[(left + right) >> 1];while (l <= r){while (a[r] > key)r--;while (a[l] <key)l++;if (l <= r){swap(a[l], a[r]);l++;r--;}}_sort(a, left, r);_sort(a, l, right);}vector<int> sortArray(vector<int>& nums) {_sort(nums, 0, nums.size() - 1);return nums;}
};

方法二：使用三指针+随机取key值

向上面那样如果直接使用快排的模板的话，如果是全部都是相同的数，或者这个数组本身就是一个有序的话，那么直接使用快排模板的话时间复杂度将会达到O(N^2)所以我们可以对快排进行优化。同样的我们也可以划分为三部分，第一部分是小于key（基准值）的，第二部分是等于key的，第三部分是大于key的。于是我们可以定义三个指针，left，cur，right，left代表第一部分的最右边，right代表第三部分的最左边，cur指针用于遍历整个数组。这样我们递归只需要对范围为[left, l]和[r, right]范围之间进行递归了。[l+ 1, r - 1]这个区间的范围是不用在进行递归了。而至于key的选取的话，我们之前都是采用第一个或者最后一个或者中间为基准值，这里我们使用使用随机选取的方式。

于是我们就可以得出这样的结论：

1. 如果nums[cur] < key，则执行swap(nums[left + 1], nums[cur])，同时对left和cur进行++
2. 如果nums[cur] == key，则只需要对cur进行++即可。
3. 如果nums[cur] > key，则执行swap(nums[right - 1], nums[cur])，同时只需要对right–即可，cur不需要进行操作，因为被交换过去的nums[right - 1]是还没进行处理的，所以还需要进一步处理。

所以上述这个优化可以将时间复杂度优化接近到NlogN的时间复杂度。

class Solution {
public:void _sort(vector<int>& nums, int left, int right){if (left >= right) return;int l = left - 1, r = right + 1; // 这样处理可以提高代码复用度int key = nums[rand() % (right - left + 1) + left];int cur = left;while (cur < r){if (nums[cur] < key){swap(nums[l + 1], nums[cur]);l++;cur++;}else if(nums[cur] == key){cur++;}else{swap(nums[r - 1], nums[cur]);r--;}}_sort(nums, left, l);_sort(nums, r, right);}vector<int> sortArray(vector<int>& nums) {_sort(nums, 0, nums.size() - 1);return nums;}
};

3. 数组中的第K个最大元素

3.1 题目来源

215.数组中的第K个最大元素

3.2 题目描述

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

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

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

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

提示：
1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104

3.3 题目解析

方法一：使用快排模板：

class Solution {
public:void _sort(vector<int>& nums, int left, int right){if (left >= right) return;int l = left, r = right;int key = nums[(left + right) >> 1];while (l <= r){while (nums[r] > key)r--;while (nums[l] < key)l++;if (l <= r){swap(nums[l], nums[r]);l++;r--;}}_sort(nums, left, r);_sort(nums, l, right);}int findKthLargest(vector<int>& nums, int k) {_sort(nums, 0, nums.size() - 1);return nums[nums.size() - k];}
};

方法二：使用三指针数据分三块+随机选取基准值

这里其实和上面几题是一样的方法，也是将数组分成三份，第一部分小于key，第二部分等于key，第三部分大于key。使用三个指针来操作，left，cur，right。left代表第一部分的最右边，right代表第三部分的最左边，cur指针用于遍历整个数组。我们假设第一部分也就是[left, l]的长度是a，第二部分也就是[l + 1, r - 1]的长度是b，第三部分也就是[r， right]的长度是c。现在我们要找到第k大的元素。所以就有一下结论

所以我们可以得出一下结论：

1. 如果c >= k，则直接在[r, right]中查找就可以了
2. 如果 c + b >= k，则直接就是返回[l + 1, r - 1] 中的任意一个值就行。
3. 如果上述1和2都不满足则需要在[left, l]中进行查找，而这个时候要查找的因该是第(k- b - c）大的数了。

class Solution {
public:int _sort(vector<int>& nums, int left, int right, int k){int l = left - 1, r = right + 1;int key = nums[rand()%(right - left + 1) + left];int cur = left;while (cur < r){if(nums[cur] < key){swap(nums[l + 1], nums[cur]);l++;cur++;}else if (nums[cur] == key){cur++;}else{swap(nums[r - 1], nums[cur]);r--;}}if (right - r + 1 >= k){return _sort(nums, r, right, k);}else if (right - l >= k){return nums[l + 1];}else{int c = right - r + 1;int b = r - l - 1;return _sort(nums, left, l, k - b - c);}}int findKthLargest(vector<int>& nums, int k) {return _sort(nums, 0, nums.size() - 1, k);}
};

4. 库存管理 III

4.1 题目来源

159. 库存管理 III

4.2 题目描述

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

1. 示例 1：
   输入：stock = [2,5,7,4], cnt = 1
   输出：[2]
2. 示例 2：
   输入：stock = [0,2,3,6], cnt = 2
   输出：[0,2] 或 [2,0]

提示：
0 <= cnt <= stock.length <= 10000
0 <= stock[i] <= 10000

4 .3 题目解析

这题其实也是使用一样的方法，使用三指针数据分三块+随机选取基准值。

class Solution {
public:void _sort(vector<int>& nums, int left, int right){if (left >= right) return;int l = left - 1, r = right + 1;int key = nums[rand() % (right - left + 1) + left];int cur = left;while (cur < r){if (nums[cur] < key){swap(nums[l + 1], nums[cur]);l++;cur++;}else if (nums[cur] == key){cur++;}else{swap(nums[r - 1], nums[cur]);r--;}}_sort(nums, left, l);_sort(nums, r, right);}vector<int> inventoryManagement(vector<int>& stock, int cnt) {vector<int> v;if (cnt == 0) return v;_sort(stock, 0, stock.size() - 1);for (int i = 0; i < cnt; i++){v.push_back(stock[i]);}return v;}
};