深圳做网站的公司哪个好,外贸都是在哪些网站做,平顶山做网站优化,国内建设网站的公司目录
分治快排算法原理
①力扣75. 颜色分类
解析代码
②力扣912. 排序数组
解析代码
③力扣215. 数组中的第K个最大元素
解析代码
④力扣LCR 159. 库存管理 III#xff08;剑指 Offer . 最小的k个数#xff09;
解析代码
本篇完。 分治快排算法原理
分治就是分而治…目录
分治快排算法原理
①力扣75. 颜色分类
解析代码
②力扣912. 排序数组
解析代码
③力扣215. 数组中的第K个最大元素
解析代码
④力扣LCR 159. 库存管理 III剑指 Offer . 最小的k个数
解析代码
本篇完。 分治快排算法原理
分治就是分而治之快排在数据结构也学过了现在来学一学三路划分快排数组划分三块 前面我们已经实现了三个版本的快速排序的算法分别是hoare法挖坑法和前后指针法。但是前面的三个版本的快速排序在某些极端场景中效率都会变得很低例如大部分都是同一个数的时候前面的三种方法都不能很高效地完成排序时间复杂度退化成了O(N^2)所以有必要对之前的排序方法进行一些改进使它能够适应包含任何数据的数组。于是就有大佬想出了一个更牛的方法那就是三路划分快排。 三路划分快排的思路三路划分顾名思义就是把数组分成三个部分进行排序在待排序数组中随机选定一个key把数组分成小于key的等于key的还有大于key的。 具体操作是 定义一个left下标为数组首元素下标的前一个位置即leftbegin-1再定义一个right下标为数组最后一个元素的下标的后一个位置即rightend1再定义一个下标curleft作为遍历数组的下标一共就leftcurright三个下标。 从a[cur]开始与key比较如果a[cur]key就用a[cur]和a[left]交换(记住这里是先后交换)然后cur如果a[cur]key,就用a[cur]和a[- -right]交换(记住这里是先减减后交换)如果a[cur]key,那就只cur即可 这样循环往复直到curright就结束最后得到的a[begin,left]是比key小的数a[left1,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.length1 n 300nums[i] 为 0、1 或 2
进阶
你能想出一个仅使用常数空间的一趟扫描算法吗
class Solution {
public:void sortColors(vectorint nums) {}
}; 解析代码
数组分三块三指针思想left i right
0 到 left 全是 0right 到 i 全是 1i 到 right 全是未处理的元素right到nums.size();全是2。
class Solution {
public:void sortColors(vectorint 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:vectorint sortArray(vectorint nums) {}; 解析代码
又是这题C语言用八大排序测试过了现在再加三指针的快排 随机选key在《算法导论》里被用概率论证明了最能让快排接近ON*logN而且下面的三路划分可以让快排最慢的情况排序重复元素ON^2直接优化成ON因为遍历一次就已经全都分到三部分中等于key的部分了。
class Solution {
public:vectorint sortArray(vectorint nums) {srand(time(nullptr)); // 随机数种子qsort(nums, 0, nums.size() - 1);return nums;}void qsort(vectorint 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(vectorint nums, int k) {}
}; 解析代码 TopK问题用堆排思路写过时间复杂度是ON*logN现在用三路划分的快排思想写一下时间复杂度是ON《算法导论》里有两页的证明。 思路在快排中当我们把数组「分成三块」之后 [begin, left] [left 1, right - 1] [right, end] 我们可以通过计算每一个区间内元素的个数进而推断出最小的 k 个数在哪些区间里面。那么我们可以直接去相应的区间继续划分数组即可。
class Solution {
public:int findKthLargest(vectorint nums, int k) {srand(time(nullptr));return qsort_topk(nums, 0, nums.size() - 1, k);}int qsort_topk(vectorint 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] [left1, 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:vectorint inventoryManagement(vectorint stock, int cnt) {}; 解析代码 之前也写过了用库里的sort排序时间是ON*logN用堆时间是ON*logK用三路划分快排思想的快速选择算法时间是ON。 当我们把数组分成三块之后可以通过计算每一个区间内元素的个数进而推断出最小的 k 个数在哪些区间里面。那么我们可以直接去相应的区间继续划分数组即可。
class Solution {
public:vectorint inventoryManagement(vectorint stock, int cnt) {srand(time(nullptr));qsort_topk(stock, 0, stock.size() - 1, cnt);return {stock.begin(), stock.begin() cnt};}void qsort_topk(vectorint 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] [left1, 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。
