Offer必备算法09_分治快排_四道力扣OJ（快排三路划分）

目录

分治快排算法原理

①力扣75. 颜色分类

解析代码

②力扣912. 排序数组

解析代码

③力扣215. 数组中的第K个最大元素

解析代码

④力扣LCR 159. 库存管理 III（剑指 Offer . 最小的k个数）

解析代码

本篇完。

---

分治快排算法原理

分治就是分而治之，快排在数据结构也学过了，现在来学一学三路划分快排（数组划分三块）：

        前面我们已经实现了三个版本的快速排序的算法，分别是hoare法，挖坑法和前后指针法。但是前面的三个版本的快速排序在某些极端场景中效率都会变得很低，例如大部分都是同一个数的时候，前面的三种方法都不能很高效地完成排序，时间复杂度退化成了O(N^2)，所以有必要对之前的排序方法进行一些改进，使它能够适应包含任何数据的数组。于是就有大佬想出了一个更牛的方法，那就是三路划分快排。

        三路划分快排的思路：三路划分，顾名思义就是把数组分成三个部分进行排序，在待排序数组中随机选定一个key，把数组分成小于key的，等于key的，还有大于key的。

        具体操作是：

• 定义一个left下标为数组首元素下标的前一个位置，即left=begin-1；
• 再定义一个right下标为数组最后一个元素的下标的后一个位置，即right=end+1；
• 再定义一个下标cur=left，作为遍历数组的下标，一共就left，cur，right三个下标。
•         从a[cur]开始与key比较，如果a[cur]<key，就用a[cur]和a[++left]交换(记住这里是先++，后交换)，然后++cur；如果a[cur]>key,就用a[cur]和a[- -right]交换(记住这里是先减减，后交换)；如果a[cur]==key,那就只++cur即可，
•         这样循环往复，直到cur=right就结束，最后得到的a[begin,left]是比key小的数，a[left+1,right-1]是等于key的数，a[right,end]是大于key的数，划分成三路之后，中间这一路就不用再进行排序了，因为中间这一路都是等于key的，所以已经有序了，只需要对左路和右路再进行递归排序即可。

---

①力扣75. 颜色分类

75. 颜色分类

难度 中等

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

进阶：

• 你能想出一个仅使用常数空间的一趟扫描算法吗？

class Solution {
public:void sortColors(vector<int>& nums) {}
};

---

解析代码

数组分三块：三指针思想：left i right，

0 到 left 全是 0，right 到 i 全是 1，i 到 right 全是未处理的元素，right到nums.size();全是2。

class Solution {
public:void sortColors(vector<int>& nums) {int left = -1, i = 0, right = nums.size();while(i < right){if(nums[i] == 0)swap(nums[++left], nums[i++]);else if(nums[i] == 1)++i;else // == 2swap(nums[--right], nums[i]);}}
};

---

②力扣912. 排序数组

912. 排序数组

难度 中等

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

• 1 <= nums.length <= 5 * 10^4
• -5 * 10^4 <= nums[i] <= 5 * 10^4

class Solution {
public:vector<int> sortArray(vector<int>& nums) {};

---

解析代码

又是这题，C语言用八大排序测试过了，现在再加三指针的快排：

        随机选key在《算法导论》里被用概率论证明了最能让快排接近O（N*logN），而且下面的三路划分可以让快排最慢的情况：排序重复元素O（N^2），直接优化成O（N），因为遍历一次就已经全都分到三部分中等于key的部分了。

class Solution {
public:vector<int> sortArray(vector<int>& nums) {srand(time(nullptr)); // 随机数种子qsort(nums, 0, nums.size() - 1);return nums;}void qsort(vector<int>& nums, int begin, int end){if(begin >= end)return;int key = nums[rand() % (end - begin + 1) + begin]; // 随机选key// rand() % (r - l + 1)是[0, n-1] 再加偏移量begin就是要排序的区间int i = begin, left = begin - 1, right = end + 1;while(i < right){if(nums[i] < key)swap(nums[++left], nums[i++]);else if(nums[i] == key)++i;else // >keyswap(nums[--right], nums[i]);}// [begin, left] [left + 1, right - 1] [right, end]qsort(nums, begin, left);qsort(nums, right, end);}
};

---

③力扣215. 数组中的第K个最大元素

215. 数组中的第K个最大元素

难度 中等

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {}
};

---

解析代码

        TopK问题，用堆排思路写过，时间复杂度是O（N*logN），现在用三路划分的快排思想写一下，时间复杂度是O（N），《算法导论》里有两页的证明。

        思路：在快排中，当我们把数组「分成三块」之后： [begin, left] [left + 1, right - 1] [right, end] ，我们可以通过计算每一个区间内元素的个数，进而推断出最小的 k 个数在哪些区间里面。那么我们可以直接去相应的区间继续划分数组即可。

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {srand(time(nullptr));return qsort_topk(nums, 0, nums.size() - 1, k);}int qsort_topk(vector<int>& nums, int begin, int end, int k){   // 到begin和end区间找第k大元素if(begin == end)return nums[begin];int key = nums[rand() % (end - begin + 1) + begin];int i = begin, left = begin - 1, right = end + 1;while(i < right){if(nums[i] < key)swap(nums[++left], nums[i++]);else if(nums[i] == key)i++;elseswap(nums[--right], nums[i]);}// [begin, left] [left+1, right-1] [rignt, end]int c = end - right + 1; // 右区间元素个数int b = right - left - 1; // 中间区间元素个数if(c >= k) // 右区间元素个数>=k，到右区间找return qsort_topk(nums, right, end, k);else if(b + c >= k) // 右两区间元素个数>=k，返回中间区间元素return key;else  // 到左区间找第k-b-c大的return qsort_topk(nums, begin, left, k - b - c);}
};

---

④力扣LCR 159. 库存管理 III（剑指 Offer . 最小的k个数）

（原：剑指 Offer . 最小的k个数）

LCR 159. 库存管理 III

难度 简单

仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。

示例 1：

输入：stock = [2,5,7,4], cnt = 1
输出：[2]

示例 2：

输入：stock = [0,2,3,6], cnt = 2
输出：[0,2] 或 [2,0]

提示：

• 0 <= cnt <= stock.length <= 10000
0 <= stock[i] <= 10000

class Solution {
public:vector<int> inventoryManagement(vector<int>& stock, int cnt) {};

---

解析代码

        之前也写过了，用库里的sort排序时间是O（N*logN），用堆时间是O（N*logK），用三路划分快排思想的快速选择算法时间是O（N）。

        当我们把数组分成三块之后，可以通过计算每一个区间内元素的个数，进而推断出最小的 k 个数在哪些区间里面。那么我们可以直接去相应的区间继续划分数组即可。

class Solution {
public:vector<int> inventoryManagement(vector<int>& stock, int cnt) {srand(time(nullptr));qsort_topk(stock, 0, stock.size() - 1, cnt);return {stock.begin(), stock.begin() + cnt};}void qsort_topk(vector<int>& arr, int begin, int end, int k){   // 把数组前k个小的丢到前面，不一定有序if(begin >= end)return ;int key = arr[rand() % (end - begin + 1) + begin];int i = begin, left = begin - 1, right = end + 1;while(i < right){if(arr[i] < key)swap(arr[++left], arr[i++]);else if(arr[i] == key)++i;elseswap(arr[--right], arr[i]);}// [begin, left] [left+1, right-1] [right, end]int a = left - begin + 1; // 左区间元素个数int b = right - left - 1; // 中间区间元素个数if(a > k)qsort_topk(arr, begin, left, k);else if(a + b >= k)return;else // 到第三区间找k - a - b小的qsort_topk(arr, right, end, k - a - b);}
};

本篇完。

此专栏下一篇是分治归并的内容，归并排序思想刷OJ。