企业官网建设流程全解析

前言

快速排序 和 归并排序的算法思路详见：【算法】常见排序算法（插入排序、选择排序、交换排序和归并排序）

一、快速排序的习题讲解

1. 排序数组（模板题，详细介绍快排算法的优化过程）

912. 排序数组

• 题目描述：

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

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

示例 ：

• 输入：nums = [5,1,1,2,0,0]
• 输出：[0,0,1,1,2,5]
• 解释：请注意，nums 的值不一定唯一。

提示：

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

• 代码示例：

classSolution{public:voidswap(int*a,int*b){inttmp=*a;*a=*b;*b=tmp;}// 使用三数取中法选择三者的中位数作为基准值并将其换到begin位置voidmedian_select(vector<int>&vec,intbegin,intend){intmid=begin+(end-begin)/2;if(vec[begin]>vec[mid])// 目标: vec[mid] >= vec[begin]swap(&vec[begin],&vec[mid]);if(vec[mid]>vec[end])// 目标: vec[end] >= vec[mid]swap(&vec[mid],&vec[end]);// 前两步，使vec[end]位置一定是最大值if(vec[begin]<vec[mid])// 目标: vec[begin] >= vec[mid]swap(&vec[begin],&vec[mid]);// 再从begin 和 end位置选出一个大的值放在begin位置，// begin位置上保存这三个位置中间的值，后续依然可以选第一个元素为基准值划分函数}// 采用三路划分的快速排序voidquicksort(vector<int>&nums,intbegin,intend){median_select(nums,begin,end);intkey=nums[begin];intleft=begin;intright=end;intcur=begin+1;while(cur<=right){if(nums[cur]<key){swap(&nums[left],&nums[cur]);left++;cur++;}elseif(nums[cur]>key){swap(&nums[right],&nums[cur]);right--;}elseif(nums[cur]==key)cur++;}if(begin<left-1)quicksort(nums,begin,left-1);if(right+1<end)quicksort(nums,right+1,end);}vector<int>sortArray(vector<int>&nums){if(nums.size()>1)quicksort(nums,0,nums.size()-1);returnnums;}};

2. 数组中的第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

• 代码演示：

classSolution{public:voidswap(int*a,int*b){inttmp=*a;*a=*b;*b=tmp;}// 使用三数取中法选择三者的中位数作为基准值并将其换到begin位置voidmedian_select(vector<int>&vec,intbegin,intend){intmid=begin+(end-begin)/2;if(vec[begin]>vec[mid])// 目标: vec[mid] >= vec[begin]swap(&vec[begin],&vec[mid]);if(vec[mid]>vec[end])// 目标: vec[end] >= vec[mid]swap(&vec[mid],&vec[end]);// 前两步，使vec[end]位置一定是最大值if(vec[begin]<vec[mid])// 目标: vec[begin] >= vec[mid]swap(&vec[begin],&vec[mid]);// 再从begin 和 end位置选出一个大的值放在begin位置，// begin位置上保存这三个位置中间的值，后续依然可以选第一个元素为基准值划分函数}// 采用三路划分的快速排序intquicksort(vector<int>&nums,intbegin,intend,intk){median_select(nums,begin,end);intkey=nums[begin];intleft=begin;intright=end;intcur=begin+1;while(cur<=right){if(nums[cur]<key){swap(&nums[left],&nums[cur]);left++;cur++;}elseif(nums[cur]>key){swap(&nums[right],&nums[cur]);right--;}elseif(nums[cur]==key)cur++;}inta=left-begin;// 小于key的元素个数intb=right-left+1;// 等于key的元素个数intc=end-right;// 大于key的元素个数if(c>=k)returnquicksort(nums,right+1,end,k);elseif(b+c>=k)returnkey;elsereturnquicksort(nums,begin,left-1,k-b-c);}intfindKthLargest(vector<int>&nums,intk){returnquicksort(nums,0,nums.size()-1,k);}};

3. 练习题：库存管理 III

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

二、归并排序的习题讲解

1. 排序数组（模板题，归并排序的算法思路）

912. 排序数组

• 题目描述：

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

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

示例 ：

• 输入：nums = [5,1,1,2,0,0]
• 输出：[0,0,1,1,2,5]
• 解释：请注意，nums 的值不一定唯一。

提示：

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

• 代码演示：

classSolution{public:// 归并排序voidmerge_sort(vector<int>&vec,intbegin,intend,vector<int>&tmp){intmid=begin+(end-begin)/2;if(begin<mid)merge_sort(vec,begin,mid,tmp);if(mid+1<end)merge_sort(vec,mid+1,end,tmp);intleft1=begin;intright1=mid;intleft2=mid+1;intright2=end;intindex=begin;while(left1<=right1&&left2<=right2){if(vec[left1]<=vec[left2]){tmp[index]=vec[left1];index++,left1++;}else{tmp[index]=vec[left2];index++,left2++;}}while(left1<=right1){tmp[index]=vec[left1];index++,left1++;}while(left2<=right2){tmp[index]=vec[left2];index++,left2++;}while(begin<=end){vec[begin]=tmp[begin];begin++;}}vector<int>sortArray(vector<int>&nums){if(nums.size()>1){vector<int>tmp(nums.size());merge_sort(nums,0,nums.size()-1,tmp);}returnnums;}};

2. 数组中的逆序对（hard）

LCR 170. 交易逆序对的总数

• 题目描述：

在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 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)。

提示：

• 0 <= record.length <= 50000

classSolution{public:// 归并排序 增加第 5 个参数：count_total（统计逆序对的个数）voidmerge_sort(vector<int>&arr,intbegin,intend,vector<int>&tmp,longlong*count_total){intmid=begin+(end-begin)/2;if(begin<mid)merge_sort(arr,begin,mid,tmp,count_total);if(mid+1<end)merge_sort(arr,mid+1,end,tmp,count_total);intleft1=begin;intright1=mid;intleft2=mid+1;intright2=end;intn=begin;while(left1<=right1&&left2<=right2){if(arr[left1]<=arr[left2]){tmp[n++]=arr[left1++];}else// 在归并排序的过程中，统计满足条件的逆序对个数{*count_total+=right1-left1+1;tmp[n++]=arr[left2++];}}while(left1<=right1){tmp[n++]=arr[left1++];}while(left2<=right2){tmp[n++]=arr[left2++];}while(begin<=end){arr[begin]=tmp[begin];begin++;}}intreversePairs(vector<int>&record){longlongcount=0;if(record.size()<2)return0;vector<int>tmp(record.size());merge_sort(record,0,record.size()-1,tmp,&count);returncount;}};

3. 计算右侧小于当前元素的个数

315. 计算右侧小于当前元素的个数

• 题目描述：

给你一个整数数组 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]

提示：

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

• 代码示例：

classSolution{public:voidmerge_sort(vector<int>&arr,intbegin,intend,vector<int>&tmp,vector<vector<int>>&index,vector<int>&ret){intmid=begin+(end-begin)/2;if(begin<mid)merge_sort(arr,begin,mid,tmp,index,ret);if(mid+1<end)merge_sort(arr,mid+1,end,tmp,index,ret);intleft1=begin;intright1=mid;intleft2=mid+1;intright2=end;intn=begin;while(left1<=right1&&left2<=right2){if(arr[left1]>arr[left2])// 在归并排序的过程中，统计满足条件的逆序对个数{index[1][n]=index[0][left1];ret[index[1][n]]+=right2-left2+1;// 增加对应下标 的逆序对个数tmp[n++]=arr[left1++];}elseif(arr[left1]<=arr[left2]){index[1][n]=index[0][left2];tmp[n++]=arr[left2++];}}while(left1<=right1){index[1][n]=index[0][left1];tmp[n++]=arr[left1++];}while(left2<=right2){index[1][n]=index[0][left2];tmp[n++]=arr[left2++];}while(begin<=end){arr[begin]=tmp[begin];index[0][begin]=index[1][begin];begin++;}}vector<int>countSmaller(vector<int>&nums){if(nums.size()==1)returnvector<int>(1,0);vector<int>ret(nums.size(),0);// 要对 index数组进行归并排序，也需要一个临时数组，// 所以直接创建两个数组，index[1]作为下标绑定数组，index[2]作为临时数组vector<vector<int>>index(2,vector<int>(nums.size()));for(inti=0;i<nums.size();i++){index[0][i]=i;}vector<int>tmp(nums.size());merge_sort(nums,0,nums.size()-1,tmp,index,ret);returnret;}};