【刷题11】分治—快速排序
目录
- 一、排序数组
- 二、颜色分类
- 三、数组中第k个最大元素
- 四、库存管理lll
一、排序数组
题目：
思路：快速排序（三路划分）
- 交换、三数取中（设置随机数，让mid更随机些）
- 三路划分：因为数组里面可能有多个相同的数，如果全是一样的数，就影响了快排的效率
代码：
class Solution {
public:
int getMid(vector<int>& nums, int left, int right)
{
int mid = left + (rand() % (right-left));
return mid;
}
// 快速排序
void QuickSort(vector<int> &nums, int left, int right)
{
if(left >= right) return;
int mid = getMid(nums, left, right);
swap(nums[mid], nums[left]);
int k = nums[left];
int begin = left, end = right, cur = left;
while(cur <= right)
{
if(nums[cur] < k)
{
swap(nums[cur], nums[left]);
++cur;
++left;
}
else if(nums[cur] > k)
{
swap(nums[cur], nums[right]);
--right;
}
else ++cur;
}
QuickSort(nums, begin, left-1);
QuickSort(nums, right+1, end);
}
vector<int> sortArray(vector<int>& nums) {
srand(time(0));
int n = nums.size();
QuickSort(nums, 0, n-1);
return nums;
}
};
二、颜色分类
题目：
思路：与上题一样
代码：
class Solution {
public:
int getMid(vector<int> &nums, int left ,int right)
{
int mid = left + (rand() % (right-left));
return mid;
}
void QuickSort(vector<int> &nums, int left, int right)
{
if(left >= right) return;
int n=nums.size();
int mid = getMid(nums, left, right);
swap(nums[mid], nums[left]);
int k = nums[left];
int begin = left, end = right, cur = left;
while(cur <= right)
{
if(nums[cur] < k)
{
swap(nums[cur], nums[left]);
cur++;
left++;
}
else if(nums[cur] > k)
{
swap(nums[cur], nums[right]);
right--;
}
else cur++;
}
QuickSort(nums, begin, left-1);
QuickSort(nums, right+1, end);
}
void sortColors(vector<int>& nums) {
srand(time(0));
QuickSort(nums, 0, nums.size()-1);
}
};
另一种写法：
class Solution {
public:
void sortColors(vector<int>& nums) {
int n = nums.size();
int left = -1, right= n, cur= 0;
while(cur < right)
{
if(nums[cur] == 0) swap(nums[cur++], nums[++left]);
else if(nums[cur] == 2) swap(nums[cur], nums[--right]);
else cur++;
}
}
};
三、数组中第k个最大元素
题目：
思路：
- 分三块与前面两题相同
- a,b,c是每块区间的元素个数
- c大于等于k：第k大在右边的区间，去右边的区间找
- b+c大于等于k：排除了在右边，那么一定在中间的区间，该区间的元素都是一样的，所以直接返回key
- 前面两个不成立，去左边的区间找，因为第k大是相对于整个数组的，而中间的和右边的区间已经确定了（第k大不会出现在中间和右边），所以k要减去中间和右边区间的个数
代码：
class Solution {
public:
int getMid(vector<int> &nums, int left, int right)
{
int mid = left + (rand() % (right-left));
return nums[mid];
}
int qsort(vector<int>& nums, int l, int r, int k)
{
if(l >= r) return nums[l];///
int key = getMid(nums, l, r);
int left = l, right = r, cur = l;
while(cur <= right)
{
if(nums[cur] < key)
{
swap(nums[cur], nums[left]);
left++;
cur++;
}
else if(nums[cur] > key)
{
swap(nums[cur], nums[right]);
right--;
}
else cur++;
}
int b = right-left+1;
int c = r - right;
if(c >= k) return qsort(nums, right+1, r, k);
else if(b+c >= k) return key;
else return qsort(nums, l, left-1, k-b-c);
}
int findKthLargest(vector<int>& nums, int k) {
srand(time(0));
int ret = qsort(nums, 0, nums.size()-1, k);
return ret;
}
};
解法二：堆
思路：建立一个小堆，先放k个元素，然后遍历剩余的元素，只要比堆顶大就进堆，往下沉。最后的堆顶就是第k大的元素
代码：
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int n = nums.size();
priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.begin()+k);
for(int i=k; i<n;i++)//从k开始，不能重复比较
{
if(nums[i] > pq.top())
{
pq.pop();
pq.push(nums[i]);
}
}
return pq.top();
}
};
四、库存管理lll
题目：
思路：快速排序—与前面相同，最后返回前cnt个元素
代码：
class Solution {
public:
int getMid(vector<int>& nums, int left, int right)
{
int mid = left+(rand()%(right-left));
return nums[mid];
}
void qsort(vector<int>& nums, int l, int r)
{
if(l >= r) return;
int key = getMid(nums, l, r);
int left = l, right = r, cur = l;
while(cur <= right)
{
if(nums[cur] < key)
{
swap(nums[cur++], nums[left++]);
}
else if(nums[cur] > key)
{
swap(nums[cur], nums[right--]);
}
else cur++;
}
qsort(nums, l, left-1);
qsort(nums, right+1, r);
}
vector<int> inventoryManagement(vector<int>& stock, int cnt) {
srand(time(0));
qsort(stock, 0, stock.size()-1);
vector<int> ret;
for(int i=0;i<cnt;i++) ret.push_back(stock[i]);
return ret;
}
};