目录
1、颜色分类
2、快速排序
3、数组中的第K个最大元素
4、库存管理III
5、排序数组
6、交易逆序对的总数
7、计算右侧小于当前元素的个数
8、翻转对
1、颜色分类
给定一个包含红色、白色和蓝色、共
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]
class Solution {
public:void sortColors(vector<int>& nums) {int key=1,i=0,left=-1,right=nums.size();while(i<right){if(nums[i]<key) swap(nums[++left],nums[i++]);else if(nums[i]==key) i++;else swap(nums[--right],nums[i]);}}
};2、快速排序
给你一个整数数组
nums，请你将该数组升序排列。你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为
O(nlog(n))，并且空间复杂度尽可能小。示例 1：
输入：nums = [5,2,3,1] 输出：[1,2,3,5]示例 2：
输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5]
class Solution {
public:vector<int> tmp;//定义全局的辅助数组帮组归并排序vector<int> sortArray(vector<int>& nums) {tmp.resize(nums.size());mergesort(nums,0,nums.size()-1);return nums;}void mergesort(vector<int>& nums,int left,int right){//递归结束条件if(left>=right) return;//选择中间开始递归 [left,mid] [mid+1,right]int mid=left+(right-left)/2;mergesort(nums,left,mid);mergesort(nums,mid+1,right);//归并排序主逻辑int cur1=left,cur2=mid+1,i=0;while(cur1<=mid&&cur2<=right){if(nums[cur1]<nums[cur2]) tmp[i++]=nums[cur1++];else tmp[i++]=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];}
};3、数组中的第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
class Solution {
public:int findKthLargest(vector<int>& nums, int k) {srand(time(NULL));return qsort(nums,0,nums.size()-1,k);}int qsort(vector<int>& nums,int l,int r,int k){if(l==r) return nums[l];//随机选keyint key=getKey(nums,l,r);//数组分三块int i=l,left=l-1,right=r+1;while(i<right){if(nums[i]<key) swap(nums[++left],nums[i++]);else if(nums[i]==key) i++;else swap(nums[--right],nums[i]);}//在三个区间内找第k大 [l,left] [left+1,right-1] [right,r]int a=r-right+1,b=right-left-1;if(a>=k) return qsort(nums,right,r,k);else if(a+b>=k) return key;else return qsort(nums,l,left,k-a-b);}int getKey(vector<int>& nums,int l,int r){return nums[rand()%(r-l+1)+l];}
};4、库存管理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]
class Solution {
public:vector<int> inventoryManagement(vector<int>& nums, int k) {srand(time(NULL));qsort(nums,0,nums.size()-1,k);return {nums.begin(),nums.begin()+k};}void qsort(vector<int>& nums,int l,int r,int k){if(l>=r) return;//随机选keyint key=GetKey(nums,l,r);//数组分三块int i=l,left=l-1,right=r+1;while(i<right){if(nums[i]<key) swap(nums[++left],nums[i++]);else if(nums[i]==key) i++;else swap(nums[--right],nums[i]);}//[l,left] [left+1,right-1] [right,l]int a=left-l+1,b=right-left-1;if(a>k) qsort(nums,l,left,k);else if(a+b>=k) return;else qsort(nums,right,r,k-a-b);}int GetKey(vector<int>& nums,int l,int r){return nums[l+(rand()%(r-l+1))];}
};5、排序数组
给你一个整数数组
nums，请你将该数组升序排列。你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为
O(nlog(n))，并且空间复杂度尽可能小。示例 1：
输入：nums = [5,2,3,1] 输出：[1,2,3,5]示例 2：
输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5]
class Solution {
public:vector<int> tmp;//定义全局的辅助数组帮组归并排序vector<int> sortArray(vector<int>& nums) {tmp.resize(nums.size());mergesort(nums,0,nums.size()-1);return nums;}void mergesort(vector<int>& nums,int left,int right){//递归结束条件if(left>=right) return;//选择中间开始递归 [left,mid] [mid+1,right]int mid=left+(right-left)/2;mergesort(nums,left,mid);mergesort(nums,mid+1,right);//归并排序主逻辑int cur1=left,cur2=mid+1,i=0;while(cur1<=mid&&cur2<=right){if(nums[cur1]<nums[cur2]) tmp[i++]=nums[cur1++];else tmp[i++]=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];}
};6、交易逆序对的总数
在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录
record，返回其中存在的「交易逆序对」总数。示例 1:
输入：record = [9, 7, 5, 4, 6] 输出：8 解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。
class Solution {
public:vector<int> tmp;int reversePairs(vector<int>& nums) {tmp.resize(nums.size());return mergesort(nums,0,nums.size()-1);}int mergesort(vector<int>& nums,int left,int right){if(left>=right) return 0;int ret=0;int mid=left+(right-left)/2;//左右俩边各找一下ret+=mergesort(nums,left,mid);ret+=mergesort(nums,mid+1,right);//归并排序(此时左右两边都是升序)，顺便左右两边找一下逆序对int i=0,cur1=left,cur2=mid+1;while(cur1<=mid&&cur2<=right) {if(nums[cur1]>nums[cur2]){tmp[i++]=nums[cur1++];ret+=right-cur2+1;}else {tmp[i++]=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];}return ret;}
};7、计算右侧小于当前元素的个数
给你一个整数数组
nums，按要求返回一个新数组counts。数组counts有该性质：counts[i]的值是nums[i]右侧小于nums[i]的元素的数量。示例 1：
输入：nums = [5,2,6,1] 输出：[2,1,1,0] 解释：5 的右侧有 2 个更小的元素 (2 和 1) 2 的右侧仅有 1 个更小的元素 (1) 6 的右侧有 1 个更小的元素 (1) 1 的右侧有 0 个更小的元素示例 2：
输入：nums = [-1] 输出：[0]示例 3：
输入：nums = [-1,-1] 输出：[0,0]
class Solution {
public://ret记录结果，index记录下标，tmp1辅助排序，tmp2辅助index跟随排序vector<int> ret,tmp1,tmp2,index;vector<int> countSmaller(vector<int>& nums) {int n=nums.size();ret.resize(n);tmp1.resize(n);tmp2.resize(n);//index初始化原数组下标index.resize(n);for(int i=0;i<n;i++) index[i]=i;mergesort(nums,0,n-1);return ret;}void mergesort(vector<int>& nums,int left,int right){if(left>=right) return;int mid=left+(right-left)/2;mergesort(nums,left,mid);mergesort(nums,mid+1,right);int i=0,cur1=left,cur2=mid+1;while(cur1<=mid&&cur2<=right) {if(nums[cur1]>nums[cur2]) {ret[index[cur1]]+=right-cur2+1;//更新结果(当前值的结果要放到其原始下标的位置)tmp1[i]=nums[cur1];//值放入辅助数组tmp2[i++]=index[cur1++];//当前值的下标放入辅助数组}else {tmp1[i]=nums[cur2];tmp2[i++]=index[cur2++];}}//解决剩余排序问题while(cur1<=mid) {tmp2[i]=index[cur1];tmp1[i++]=nums[cur1++];}while(cur2<=right) {tmp2[i]=index[cur2];tmp1[i++]=nums[cur2++];}for(int i=left;i<=right;i++){nums[i]=tmp1[i-left];index[i]=tmp2[i-left];}}
};8、翻转对
给定一个数组
nums，如果i < j且nums[i] > 2*nums[j]我们就将(i, j)称作一个重要翻转对。你需要返回给定数组中的重要翻转对的数量。
示例 1:
输入: [1,3,2,3,1] 输出: 2示例 2:
输入: [2,4,3,5,1] 输出: 3
class Solution {
public:vector<int> tmp;int reversePairs(vector<int>& nums) {tmp.resize(nums.size());return mergesort(nums,0,nums.size()-1);}int mergesort(vector<int>& nums,int left,int right){if(left>=right) return 0;int ret=0;int mid=left+(right-left)/2;//左右俩边各找一下ret+=mergesort(nums,left,mid);ret+=mergesort(nums,mid+1,right);//在归并前找翻转对(数组有序，同向双指针)int i=0,cur1=left,cur2=mid+1;while(cur1<=mid&&cur2<=right) {if(nums[cur1]>2*(long long)nums[cur2]){ret+=right-cur2+1;cur1++;}else cur2++;}//归并排序i=0,cur1=left,cur2=mid+1;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];}return ret;}
};
的对象创建机制)