快速选择与快速排序的区别：
- 快速排序：递归地对数组的左右两部分进行排序。
- 快速选择：只递归处理包含第
k个元素的那一部分，目标是找到第k大的元素，而不是对整个数组排序。
快排
void quickSortHelper(vector<int>& nums, int left, int right) {
if (left >= right) return; // 如果子数组的长度小于或等于 1，已经排序
// 划分操作
int pivotIndex = partition(nums, left, right);
// 递归对左右两部分进行排序
quickSortHelper(nums, left, pivotIndex - 1);
quickSortHelper(nums, pivotIndex + 1, right);
}
int partition(vector<int>& nums, int left, int right) {
// 选择 pivot（本例选择最右边的元素作为 pivot）
int pivot = nums[right];
int i = left - 1;
// 遍历数组，调整小于和大于 pivot 的元素的位置
for (int j = left; j < right; ++j) {
if (nums[j] <= pivot) {
// 将小于或等于 pivot 的元素放到数组的左边
swap(nums[++i], nums[j]);
}
}
// 将 pivot 放到它最终应该在的位置
swap(nums[i + 1], nums[right]);
return i + 1; // 返回 pivot 的最终位置
}1.数组中第k大的数-快速选择
https://leetcode.cn/problems/kth-largest-element-in-an-array/description/?envType=study-plan-v2&envId=top-100-liked腾讯面经高频真题，这题看上去不难，但是难点是复杂度规定为O（n）
如果用sort的话 就是O（nlogn）能做出来不太合规就是
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(),nums.end());
return nums[int(nums.size())-k];
}
};想要得到O(n)，就要用快速选择算法，但是只能收敛于O(n)。
思想
- 选取基准元素：像快速排序一样，从数组中选择一个基准元素。
- 分区：将数组分成两部分，一部分小于基准，一部分大于基准。
- 判断基准位置：
- 如果基准的位置刚好是
k，则返回该元素。 - 如果
k小于基准位置，递归地在左半部分查找。 - 如果
k大于基准位置，递归地在右半部分查找。
- 如果基准的位置刚好是
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
srand(time(NULL)); // 初始化随机数生成器
return quickSelect(nums, 0, nums.size() - 1, k - 1); // 调用快速选择函数
}
private:
int quickSelect(vector<int>& nums, int left, int right, int k) {
// 选择中点作为 pivot
int pivot = nums[left + (right - left) / 2];
int i = left, j = right;
// 双指针划分
while (i <= j) {
while (nums[i] > pivot) i++; // 找到左边小于 pivot 的元素
while (nums[j] < pivot) j--; // 找到右边大于 pivot 的元素
if (i <= j) {
swap(nums[i], nums[j]); // 交换
i++;
j--;
}
}
// 根据 k 的位置决定继续在左半边还是右半边递归
if (left <= k && k <= j) return quickSelect(nums, left, j, k); // 左边部分
if (i <= k && k <= right) return quickSelect(nums, i, right, k); // 右边部分
return nums[k]; // 找到 k 位置的元素
}
};
2.统计字符串含有大写字母A的个数
