1.颜色分类
思路：定义三个变量，i用来遍历数组，left标记0区域的最右测，right标记2区域的最左侧
分成了4段区间
[0, left]： 全是0。
[left + 1, i - 1]：全是1。
[i, right - 1]：待扫描的元素。
[right, n - 1]：全是2。
用i遍历数组时，num[i] == 0时交换++left和i++的值
num[i] == 1时 i++。
nums[i] == 2时， right--，i不变因为[i, right - 1]区间内是带扫描的元素。
注意：初始化时left = -1， right = nums.size()。因为要保证前面的四段区间
class Solution
{
public:
void sortColors(vector<int>& nums)
{
int left = -1, right = nums.size();
int i = 0;
while(i < right)
{
if(nums[i] == 0)
swap(nums[++left], nums[i++]);
else if(nums[i] == 1)
i++;
else if(nums[i] == 2)
swap(nums[--right],nums[i]);
}
}
};2.排序数组
思路：采用三路划分，用随机数取key
用i遍历时，num[i] < key时交换++left和i++的值。
num[i] == key时 i++。
nums[i] > key时， right--，i不变因为[i, right - 1]区间内是带扫描的元素。
[l, left] : 所有 < key 的元素
[left+1, right-1] : 所有 == key 的元素
[right, r] : 所有 > key 的元素class Solution
{
public:
vector<int> sortArray(vector<int>& nums)
{
srand(time(NULL));
qsort(nums, 0, nums.size() - 1);
return nums;
}
void qsort(vector<int> &nums, int l, int r)
{
if(r <= l) return;//退出条件
int x = rand();
int key = nums[x % (r - l + 1) + l];
int i = l;
int left = l - 1, right = r + 1;
while(i < right)
{
if(nums[i] < key)
{
swap(nums[++left], nums[i++]);
}
else if(nums[i] == key)
{
i++;
}
else
{
swap(nums[--right], nums[i]);
}
}
//[l, left] [left + 1, right - 1] [right, r]
qsort(nums, l, left);
qsort(nums, right, r);
}
};3.数组中的第k个最大元素
思路：快速选择算法 时间复杂度O(N)
1. 随机枢轴选择：key = nums[rand() % (r - l + 1) + l]
2. 三路划分：
- 小于 key 的部分：
[l, left] - 等于 key 的部分：
[left+1, right-1] - 大于 key 的部分：
[right, r]
3.分情况讨论
- 如果第 k 大元素在右边部分：
c = r - right + 1 >= k - 如果在中间部分：
b + c >= k（直接返回 key） - 否则在左边部分：递归处理左侧子数组
该算法的时间复杂度为 O(N) 主要基于：
- 线性时间完成每次划分
- 随机枢轴确保平均每次将问题规模减半
- 算法只沿一个递归路径深度搜索
- 三路划分高效处理重复元素
class Solution {
public:
int findKthLargest(vector<int>& nums, int k)
{
srand(time(NULL));
return qsort(nums, 0, nums.size() - 1, k);
}
int qsort(vector<int>& nums, int l, int r, int k)
{
if(l == r) return nums[l];
int left = l - 1, right = r + 1, i = l;
int key = nums[rand() % (r - l + 1) + l];//随机取key
//三路划分
while(i < right)
{
if(nums[i] < key) swap(nums[++left], nums[i++]);
else if(nums[i] == key) i++;
else swap(nums[--right], nums[i]);
}
//分类讨论
int c = r - right + 1, b = right - left - 1;
if(c >= k) return qsort(nums, right, r, k);
else if(b + c >= k) return key;
else return qsort(nums, l, left, k - c - b);
}
};4.库存管理
LCR 159. 库存管理 III - 力扣（LeetCode）
思路：快速选择算法，将比cnt小的数都放在key前面，前面的数只保持小于key不保持有序。
总体代码思路和第三题代码相似
class Solution
{
public:
vector<int> inventoryManagement(vector<int>& stock, int cnt)
{
srand(time(NULL));
qsort(stock, 0, stock.size() - 1, cnt);
vector<int> ret(stock.begin(), stock.begin() + cnt);
return ret;
}
void qsort(vector<int> &stock, int l, int r, int k)
{
if(l >= r)
return ;
int key = stock[rand() % (r - l + 1) + l];
int left = l - 1, right = r + 1, i = l;
while(i < right)
{
if(stock[i] < key) swap(stock[++left], stock[i++]);
else if(stock[i] == key) i++;
else swap(stock[--right], stock[i]);
}
int a = left - l + 1, b = right - left - 1;
if(a > k) qsort(stock, l, left, k);
else if(a + b >= k) return;
else qsort(stock, right, r, k - a -b);
}
};