若 nums[cur] == 0:交换 left+1 与 cur 位置元素,left++,cur++;
若 nums[cur] == 1:无需交换,直接 cur++;
若 nums[cur] == 2:交换 right-1 与 cur 位置元素,right--,cur 不变(因为交换后的元素未扫描)。
classSolution {
public:
voidsortColors(vector<int>& nums){
int n = nums.size();
int left = -1, right = n, cur = 0;
while (cur < right) {
if (nums[cur] == 0) swap(nums[++left], nums[cur++]);
(nums[cur] == ) cur++;
(nums[--right], nums[cur]);
}
}
};
classSolution {
public:
intfindKthLargest(vector<int>& nums, int k){
returnqsort(nums, 0, nums.size() - 1, k);
}
intqsort(vector<int>& nums, int l, int r, int k){
if (l == r) return nums[l];
int key = getRandom(nums, l, r);
int left = l - 1, right = r + 1, cur = l;
while (cur < right) {
if (nums[cur] < key) swap(nums[++left], nums[cur++]);
elseif (nums[cur] == key) cur++;
elseswap(nums[--right], nums[cur]);
}
int c = r - right + 1, b = right - 1 - (left + 1) + 1;
if (c >= k) returnqsort(nums, right, r, k);
elseif (b + c >= k) return key;
elsereturnqsort(nums, l, left, k - b - c);
}
intgetRandom(vector<int>& nums, int l, int r){
return nums[rand() % (r - l + 1) + l];
}
};
classSolution {
public:
vector<int> smallestK(vector<int>& arr, int k){
srand(time(NULL));
qsort(arr, 0, arr.size() - 1, k);
return {arr.begin(), arr.begin() + k};
}
voidqsort(vector<int>& arr, int l, int r, int k){
if (l >= r) return;
int key = getRandom(arr, l, r);
int left = l - 1, right = r + 1, cur = l;
while (cur < right) {
if (arr[cur] < key) swap(arr[++left], arr[cur++]);
elseif (arr[cur] == key) cur++;
elseswap(arr[--right], arr[cur]);
}
int a = left - l + 1, b = right - 1 - (left + 1) + 1;
if (a > k) qsort(arr, l, left, k);
elseif (a + b >= k) return;
elseqsort(arr, right, r, k - a - b);
}
intgetRandom(vector<int>& arr, int l, int r){
return arr[rand() % (r - l + 1) + l];
}
};
二、归并排序(Merge Sort)
归并排序完美体现了【分而治之】的思想:先递归分解到长度为 1,再合并有序数组。
1. 排序数组
思路解析:
分:取中点,将数组一分为二;
治:合并两个较短的有序数组。
classSolution {
vector<int> tmp;
public:
vector<int> sortArray(vector<int>& nums){
tmp.resize(nums.size());
mergeSort(nums, 0, nums.size() - 1);
return nums;
}
voidmergeSort(vector<int>& nums, int left, int right){
if (left >= right) return;
int mid = (right + left) >> 1;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
int cur1 = left, cur2 = mid + 1, i = 0;
while (cur1 <= mid && cur2 <= right) {
tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
}
while (cur1 <= mid) tmp[i++] = nums[cur1++];
while (cur2 <= right) tmp[i++] = nums[cur2++];
for (int i = left; i <= right; i++) nums[i] = tmp[i - left];
}
};