偃师市住房和城乡建设局网站,网站个人主页怎么做,能打开任何网站的浏览器,沛县网站一、颜色分类
题目链接:
75. 颜色分类 - 力扣#xff08;LeetCode#xff09;
题目介绍#xff1a;
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums #xff0c;原地 对它们进行排序#xff0c;使得相同颜色的元素相邻#xff0c;并按照红色、白色、蓝色顺序…一、颜色分类
题目链接:
75. 颜色分类 - 力扣LeetCode
题目介绍
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums 原地 对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。 n nums.length1 n 300nums[i] 为 0、1 或 2
思路
这个题目的要求其实就是将0放到最左边将1放到中间将2放到最后边思路就是将数组划分为三个部分 设数组大小为 n 定义三个指针 left, cur, right : 在 cur 往后扫描的过程中保证 [0, left内的元素都是 0 [left , cur - 1] 内的元素都是 1 [cur, right] 内的元素是待定元素 right, n] 内的元素都是 2 。
当cur遍历到0交换nums[cur]和nums[left],由于交换前left所指元素一定是1所以cur和left都可以。
当cur遍历到1cur;
当cur遍历到2交换nums[cur]和nums[right],right可以--但是由于交换前right所指元素依旧是待定元素所以cur不能还要判断一下
class Solution {
public:void sortColors(vectorint nums) {int left 0;int right nums.size()-1;int curleft;while (cur right) {if (nums[cur] 0) {swap(nums[left], nums[cur]);left;cur;} else if (nums[cur] 1) {cur;} else {swap(nums[cur], nums[right]);right--;}}}
};
二、快速排序
题目链接:
912. 排序数组 - 力扣LeetCode
题目介绍
给你一个整数数组 nums请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题时间复杂度为 O(nlog(n))并且空间复杂度尽可能小。 1 nums.length 5 * 10^4-5 * 104 nums[i] 5 * 10^4
思路
与上面的题思路相同不过我们需要先选择一个基准元素让这个基准元素左边都是小于他的值右边都是大于他的值这样这个基准元素在数组中就排序好了。接下来就是排序左边的区间和右边的区间。
注意数组中选择的那个基准元素可能存在很多个一轮排序后 [left,right] 区间都是key所以这段区间都不需要排序了只需要排【beginleft-1】和【right1end】区间。
假设一个数组全是一样的值这样三路划分的效率就很块因为cur就会不断向后遍历直到碰到right(end),其效率就是O(N)
class Solution {
public:vectorint sortArray(vectorint nums) {qsort(nums,0,nums.size()-1);return nums;}void qsort(vectorint nums, int begin, int end) {// 进了这个区间一定能找到if (begin end)return;int key nums[begin];int left begin;int right end;int cur left 1;// 分成三块while (cur right) {if (nums[cur] key) {swap(nums[left], nums[cur]);} else if (nums[cur] key) {cur;} else {swap(nums[right--], nums[cur]);}}qsort(nums, begin, left - 1);qsort(nums, right 1, end);}
};
三、数组的第K个最大元素
题目链接
215. 数组中的第K个最大元素 - 力扣LeetCode
题目介绍
给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。
请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 1 k nums.length 105-104 nums[i] 10
思路
首先我们可以选择一个基准元素采用三路划分排序一遍此时 key的位置就排序好了虽然此时他的左右两边都是无序的但是此时我们可以判断一下如果右边的元素个数大于等于k那说明第k大的元素就在右边那我们就不用管左边了如果中间的元素加上右边的元素才大于等于k那说明第k大的元素就是key否则我们就到左边找第( k-右边元素数量-中间元素数量)大的元素这样的算法是非常快的因为我们不需要将数组完全的排好序。
其次只要进入到了某个区间找元素那就说明这值一定在这个区间中所以当beginend时我们就可以返回nums[begin]
class Solution {
public:int findKthLargest(vectorint nums, int k) {return qsort(nums,0,nums.size()-1,k);}int qsort(vectorint nums,int begin,int end,int k){//进了这个区间一定能找到if(beginend)return nums[begin];int keynums[begin];int leftbegin;int rightend;int curleft1;//分成三块while(curright){if(nums[cur]key){swap(nums[left],nums[cur]);}else if(nums[cur]key){cur;}else{swap(nums[right--],nums[cur]);}}int cend-right;int bright-left1;if(ck)return qsort(nums,right1,end,k);else if(bck)return key;else return qsort(nums,begin,left-1,k-b-c);}
};
四、数组中最小的k个数
题目链接:
LCR 159. 库存管理 III - 力扣LeetCode
题目介绍
仓库管理员以数组 stock 形式记录商品库存表其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量返回 顺序不限。 思路
与上一题的思路一样我们先选择一个基准元素采用三路划分将数组分为左中右三部分如果左边的数量大于等于k那说明最小的k个数就在左边就到左边找中间和右边不管了。如果左边和中间加起来的数量才大于等于k那就可以直接返回因为前k个元素已经在左边和中间了虽然他们不是完全有序的。否则的话我们就要到右边找最小的k-a-b个数了
class Solution {
public:vectorint inventoryManagement(vectorint nums, int k) {qsort(nums,0,nums.size()-1,k);return {nums.begin(),nums.begin()k};}void qsort(vectorint nums,int begin,int end,int k){if(beginend) return;int keynums[begin];int leftbegin,rightend;int curleft1;//分为三块while(curright){if(nums[cur]key)swap(nums[left],nums[cur]);else if(nums[cur]key)cur;elseswap(nums[right--],nums[cur]);}// 判断int aleft-begin;int bright-left1;if(ak) qsort(nums,begin,left-1,k);else if(abk) return;else qsort(nums,right1,end,k-a-b);}
};
