快速选择与快速排序的区别：
- 快速排序：递归地对数组的左右两部分进行排序。
- 快速选择：只递归处理包含第
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) {// 选择中点作为 pivotint 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的个数