力扣刷题笔记 #07 贪心算法

本文最后更新于:2025年3月9日 晚上

本文包含「贪心算法」类型题中的:扫描贪心、置换环贪心、单调队列贪心、排序贪心等。持续更新中。

题目描述

方法1

方法2

方法3

坑点

满足「重叠子问题 + 贪心选择性」的问题。通常涉及一定的思维量,以及巧妙的构造

扫描贪心

31. 下一个排列 (M)

题目描述:给定整数数组的一个排列,生成字典序的下一个排列。数字可能有重复,要求原地修改

方法1:贪心 + 两次反向扫描,第一次扫描找到首个「下降数」,将该数与右边的数交换就能将排列变大;第二次找到「比下降数大的第一个数」,将两数交换,右边的数字逆序即可。时间复杂度 \(O(n)\)

由于按字典序的下一个排列会比当前要大,但是要让变大的幅度尽可能小。观察排列的变化规律,发现从后往前一直会有递增关系,直到遇到第一个下降数(且不能是相等的)。可以证明,如果只改变「下降数」右边的序列,结果不可能更大。

因此必须取代下降数,而每次取代下降数的则是右边一个比之稍大的数(同样不能是相等的,否则交换没有意义)。将两数交换后,整个排列必然会增大,为了能让变大的幅度尽可能小,右边的序列就需要逆序成升序序列

但是如果没有找到下降数,则说明整个序列已经是降序,此时直接逆转即可。

方法2:C++ 函数 netx_permutation(a,a+n) 实现了方法 1 的功能。

55. 跳跃游戏 (M)

题目描述:给定一个非负整数数组,数组中的每个元素代表在该位置可以跳跃的最大长度,判断能否从第一个元素跳到最后一个元素。

方法1:贪心,只需考虑向前跳(向后跳意味着循环)。为了不漏掉每个可能的转移,需要扫描跳跃范围内的所有元素,贪心维护「能跳到的最右范围」,每次遇到更大的就更新。时间复杂度 \(O(n)\),空间复杂度 \(O(1)\)

方法2:贪心,维护「剩余还能跳的步数」,逐步递减,每次遇到更大的就更新。时间复杂度 \(O(n)\),空间复杂度 \(O(1)\)

670. 最大交换 (M)

题目描述:给定一个非负整数,至多可以交换一次数字中的任意两位,返回能得到的最大值。

方法1:暴力,遍历所有可能的交换方式,复杂度 \(O(k^2)\)\(k\) 为位数。

方法2:贪心,每一个数字只能和其左侧相对小的数字交换,且不能跨越比它更大的数字,因为比它更大的数字往左交换的收益更高。因此从右往左扫描,记录当前最大的数及其可以交换的最远距离,复杂度 \(O(k)\)

扩展:这类问题需要把整数当作序列来操作,可以结合 to_string()stoi() 函数。

11. 盛最多水的容器 (M)

题目描述:给定一个长度为 n 的数组表示 n 条垂线的高,找出其中两条线,使它们构成的容器能装最多的水。

方法1:暴力,两层循环,先选中左边界,再遍历右边界,时间复杂度 \(O(n^2)\)

方法2:贪心 + 对撞双指针,双指针从两端开始遍历,选定两个边界中的短板,向中间收窄一格。时间复杂度 \(O(n)\)

贪心选择性证明:在每个状态下,无论长板或短板向中间收窄一格,都会导致水槽底边宽度变短。

  • 若向内移动短板 ,水槽的短板可能变大,因此下个水槽的面积可能增大
  • 若向内移动长板 ,水槽的短板不变或变小,因此下个水槽的面积一定变小

因此每轮向内移动短板,都会消去「不可能成为最大值的状态」。

42. 接雨水 (H)

题目描述:给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

方法1:暴力,对于每个坐标,其能接的水量取决于左右两边最高的柱子中较矮者,两层循环遍历,复杂度 \(O(n^2)\)

方法2:DP 预处理最大值,两次扫描,记录每个柱子左右两边最大值,再扫描累计,时空复杂度均为 \(O(n)\)。该方法可以简单优化:从左到右的预处理可以和第三次扫描合并用一个变量存储左边最大值,节省一个数组。

方法3:单调不增栈 + 模拟,每遍历到一个柱子,如果小于等于栈顶元素则入栈,如果更大则说明前面的柱子可以形成水洼,则依次将所有较小数弹出,并计算栈顶元素和新柱子的距离差值(表示水洼的左右墙壁,如果此时栈空,则表示没有左墙,该水洼不成立),再把新柱子入栈。时空复杂度均为 \(O(n)\)

方法4:贪心 + 对撞双指针,双指针从两端开始遍历,再用两个变量存储左右两边最大值,每次最值较小者向中间收窄一格,同时计算出当前柱子能接的水量(当前柱子与这一侧最值的高度差,该值就是当前柱子能接到的最大水量)。时间复杂度 \(O(n)\),空间复杂度 \(O(1)\)

最值较小侧可以先计算的原因是:每个位置能接的水量取决于左右两边最高的柱子中较矮者,而最值较小侧的指针所指的位置,其所在侧的最值已经是较矮的(确定性),另一侧的最值未知但只会变得更大,所以此时该位置的答案已经可以提前确定。

581. 最短无序连续子数组 (M)

题目描述:给定一个整数数组,从中找出一个最短连续子数组,如果对这个子数组排序,那么整个数组都会变为升序。

方法1:索引排序,对整个数组进行索引排序,再从两边扫描第一个 idx[i]!=i 的位置,时间复杂度 \(O(n\log n)\)。为了防止重复数导致不稳定,应采用 stable_sort()

方法2:贪心,从左往右扫描并维护最大值,如果新遇到一个元素小于最大值,则该元素必定无序,扩展右边界;同理,从右往左维护最小值,扩展左边界。时间复杂度 \(O(n)\)

贪心选择性证明:整个数组必定会呈现「有序 + 无序 + 有序」的排列,而无序段的所有元素都要大于左段的最大值、小于右段的最小值。

因此,从左往右扫描时如果遇到一个元素小于最大值,则其不可能处于右段(因为右段必须更大、且升序),不可能处于左段(因为左段必须升序),则其必定在无序段中。

621. 任务调度器 (M)

题目描述:给定一个字符数组表示任务列表,每个大写母代表一种不同种类的任务,任务可以按任何顺序执行,每次执行需要一个单位时间。但两个相同种类的任务之间需要有 n 的冷却时间。计算完成所有任务所需的最短时间。

方法1:贪心 + 构造,先用桶记录下每种任务出现的次数,再降序排列。最后按照如下方式构造解:

假设出现最多的任务是 \(A\),则至少要形成 \(A** +A**+A\) 的序列,为了尽量利用空间,我们要将剩余任务插入\(*\) 位置。此时最短长度为 \((hash[A]-1)\times (n+1)+1\)

注意到如果其他任务的次数和 \(A\) 一样多,则会形成 \(AB*+AB*+AB\) 的序列,即末尾扩充。而如果其他任务比 \(A\) 少,直接插入到空位即可,必然会满足冷却时间。

当所有 \(*\) 位置都插满后,剩余的任务可以直接补到每一组子序列之后,例如 \(ABCD+ABCD+AB\),此时所有的 \(D\) 之间间隔都大于 n,且无需新的 \(*\) 占位。此时答案就是 tasks 的总数。

原创. 相邻字母不相同的最长字符串 (M)

题目描述:给定 26 个数字,分别表示字母 a-z 的数量,用这些字符拼接成相邻字母不相同的字符串,求最长字符串长度。

方法1:贪心,制约总长度的关键因素在于数量最多的字符,如果它的数量比其余字符的总和多 1 个则恰好可以交错排列,否则就无法将其全部放入。其次,如果其他字符的总和超过它,则多余字符可以插进序列的前部。因此,扫描维护所有字符的总数 sum,找出最多字符数 max_cnt。如果最大值超过剩余字母数量加 1,则最长字符串长度为 2 * (sum - max_cnt) + 1。否则,可以完全利用所有字母,长度为 sum。时间复杂度 \(O(n)\)

135. 分发糖果 (H)

题目描述:给定大小为 n 的数组表示 n 个孩子的评分,要求每个孩子至少分到一个糖果,且相邻两个孩子评分更高的孩子会获得更多的糖果,求最少需要的糖果数目。

方法1:记忆化搜索,DFS 终止条件是相邻点评分大于等于当前点,否则就先 DFS 求出邻居的结果。用 vis 数组记录访问过的点,时空复杂度均为 \(O(n)\)

方法2:贪心 + 两遍扫描,第一遍从左到右扫描,初始化一个全 1 的数组 left,再对所有 r[i]<r[i+1] 的情况维护,其他情况不变;同理从右到左维护一个 right,最后取二者中最大值即为答案。时空复杂度均为 \(O(n)\)

贪心选择性证明:任取序列中相邻的两点 A 和 B,如果 A < B,则从左到右扫描后,B 的糖果一定比 A 多;且从右到左扫描后,A 的糖果不会变得更多,因此满足两个规则。同理 A > B 也成立,而当 A = B 时,二者的值不相互影响。综上所述,取最大值后两个规则都能成立。

方法3:贪心 + 一遍扫描,同时考虑两个规则,从左到右遍历,如果当前处于递增序列,则持续增一;如果处于递减序列,则每次增加「递减序列的长度」的量。时间复杂度 \(O(n)\),空间复杂度 \(O(1)\)

坑点:方法 1 要注意相邻的评分如果相等,糖果数可以任意取值,因此相等时递归就可以停止了(只需看另一边,两边都相等时直接取 1)。如果相等时仍进行递归,由于相等具有对称性,会互相递归导致死循环!

置换环贪心

置换环是线性扫描贪心中的一系列经典问题,背景是计算「使一个无重复数组有序的最小交换次数」。例如在数组 \([2,0,1,4,3]\) 中,\([2,0,1]\)\([4,3]\) 分别是两个置换环,将每个置换环排序的代价是 \(length-1\),因此将整体排序的代价就是「数组长度减去置换环的个数」。有两种做法:

  • 目标序列的下标用哈希表映射存储 hash[value]=index,遍历原序列,将不在位元素交换到目标位置,并使得当前位置的目标元素归位
  • 计算环的个数,需要将数组离散化到 \(0-N\)标记访问过的元素,对每个未访问的元素 for(auto a: nums),继续访问 a = nums[a],直到绕环一周。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// nums 中无重复元素
int getMinSwaps(vector<int>& nums) {
unordered_map<int, int> hash;
vector<int> sortedNums(nums);
sort(sortedNums.begin(), sortedNums.end());
for (int i = 0; i < sortedNums.size(); i++)
hash[sortedNums[i]] = i;

int cnt = 0;
for (int i = 0; i < nums.size(); i++) {
while(nums[i] != sortedNums[i]){
swap(nums[i], nums[hash[nums[i]]]);
cnt++;
}
}
return cnt;
}
// 如果 nums 是 0 到 n-1 的元素,可以直接原地哈希
int getMinSwaps(vector<int>& nums) {
int cnt = 0;
for (int i = 0; i < nums.size(); i++) {
while(nums[i] != i){
swap(nums[i], nums[nums[i]]);
cnt++;
}
}
return cnt;
}

2471. 逐层排序二叉树所需的最少操作数目 (M)

题目描述:给定一颗 \(N\) 个节点的二叉树,树上节点的取值无重复,计算将每层二叉树节点排序所需的最少交换次数

方法1:层序遍历 + 哈希表,先遍历取出每一层的元素形成嵌套数组。对每个数组先排序得到目标序列,再用哈希表记录每个元素的目标位置(无重复),将原数组遍历并交换不在位元素,复杂度 \(O(n\log n)\)

方法2:层序遍历 + 置换环,对每个数组先排序,再离散化,使用访问数组绕环访问,时间复杂度 \(O(n\log n)\)

拓展:任何「取值无重复的排序所需的最少交换次数」其实就是置换环问题!

765. 情侣牵手 (H)

题目描述n 对情侣随机坐在连续的 2n 个座位上,假设情侣对按顺序编号,第一对是 0,1,第二对是 2,3 以此类推,求最少交换座位的次数,使得每对情侣可以并肩坐在一起

方法1:置换环 + 并查集,将数组两两分组,错误配对的情侣必然位于一个置换环,而总共需要交换的次数就是「总情侣对数 - 置换环的个数」,通过并查集找出置换环,时间复杂度 \(O(n \log n)\),空间复杂度 \(O(n)\)

方法2:置换环 + BFS,将置换环视为连通分量,通过 BFS 和访问数组 \(vis\) 找出所有连通分量,时间复杂度 \(O(n)\)

方法3:哈希表 + 贪心,用哈希表(数组)记录每个序号所在的位置,每次遍历一个情侣对,如果错误配对,则将不在位的序号交换到当前位置,并更新哈希表,可以证明每次交换都是「必要的」,时间复杂度 \(O(n)\)

单调队列贪心

单调队列贪心是扫描贪心的一种特殊情况,需要在扫描的过程中维护一个单调递增/递减的队列。扫描的同时在队列中进行二分查找、尾部插入等操作,最终结果与队列长度队列元素相关。

注意区分单调栈和单调队列,前者包含了栈的连续弹出操作,用来排除所有不可能成为下一个最大/最小值的元素;后者则维护一个可持续的队列(可以用数组、栈、双端队列实现)。

300. 最长递增子序列 (LIS) (M)

题目描述:一个整数数组 nums,找到其中最长严格递增子序列的长度。(子序列可以不连续)

方法1:DP,定义 \(dp[i]\)\(nums[i]\) 结尾的 LIS 长度,每次从 \(dp[j]\) 中找满足条件的最大值转移,复杂度 \(O(n^2)\)\[ d p[i]=\max (d p[j])+1 \text {, 其中 } 0 \leq j<i \text { 且 } n u m[j]<n u m[i] \] 方法2:贪心 + 单调队列二分查找,要使 LIS 尽可能的长,就需要让序列上升得尽可能慢,因此我们希望每次在 LIS 末尾元素尽可能的小。因此维护一个数组 \(d[i]\) 表示长度为 \(i\) 的 LIS 的末尾元素的最小值(初始化为正无穷),每新来一个元素就将其二分查找到其可以放入的位置,并更新 \(d\) 数组。复杂度 \(O(n \log n)\)

显然 \(d[i]\)单调严格递增的,反证:如果 \(d[i] \geqslant d[j]\)\(i < j\),则可以将 \(d[j]\) 对应的 LIS 删除 \(j-i\) 个数使其长度变为 \(i\),但显然此时末尾元素满足 \(d[i] \geqslant d[j] \geqslant d[i]'\),则 \(d[i]\) 与其定义相矛盾。

769. 最多能完成排序的块 (M)

题目描述:给定一个长度为 n 的数组表示 \([0, n-1]\) 的整数的一个排列。现将数组分为若干大小不等的块,并对每个块单独排序,且排序后的结果和整个数组排序的结果相同。计算数组能划分的最多块数

方法1:贪心 + 一次遍历,由于数组是一个无重复的全排列,每个数就是其排序后对应的下标。因此维护一个变量 mx 表示已遍历过的数中的最大值(分块的上限),如果 mx 与当前遍历到的下标 i 相等,说明可以进行一次分块。时间复杂度 \(O(n)\),空间复杂度 \(O(1)\)

方法2:贪心 + 单调队列,方法 1 要求数组是无重复的全排列,如果数字不连续、有重复就无法实现下标的对应关系。观察发现从左到右,每个分块都有一个最大值,并且这些最大值呈单调递增。因此可以用一个单调队列,时空复杂度均为 \(O(n)\)

当栈为空,或遍历到的数 x 大于等于栈顶元素时直接入栈;

如果 x 小于栈顶元素 t,则需要把栈中大于 x 的元素弹出,再放回 t,表示「介于 xt 之间」的分块融合。由于有放回的操作,所以本题实质上是单调队列而非单调栈。

最终返回栈的大小。

768. 最多能完成排序的块 II (H)

题目描述:同上一题类似,但数组大小、元素取值范围更大,且可能出现重复元素

方法1:排序 + 哈希表,将原数组复制并排序,同时遍历两个数组,用哈希表记录出现过的元素及频次,如果在原数组出现过,则频次加一;在排序数组出现过,则频次减一。当频次为 0 时 erase 元素,如果哈希表为空,则表示划分出了一个新的块。时间复杂度 \(O(n\log n)\),空间复杂度 \(O(n)\)

方法2:索引排序,将原数组进行索引排序得到 \(idx\),此时 \(idx\) 即为 \([0,n-1]\)全排列,因此可以用一次遍历完成。时间复杂度 \(O(n\log n)\),空间复杂度 \(O(\log n)\),均为快排的开销

方法3:贪心 + 单调队列,同上一题的方法 2,时空复杂度均为 \(O(n)\)

239. 滑动窗口最大值 (H)

题目描述:给定一个整数数组 nums,一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。每次移动一位,返回每次滑动窗口中的最大值

方法1:优先队列,窗口内维护一个大顶堆,每次将堆顶元素作为答案。当窗口移动时,新元素放入,旧元素懒弹出,即当旧元素成为堆顶时再弹出。因此优先队列需要放入元素值和下标,用于判断旧元素是否不在窗口内。由于队列长度最长为 \(n\),时间复杂度 \(O(n\log n)\),空间复杂度 \(O(n)\)

方法2:贪心 + 单调队列,窗口内维护一个单调队列,存放可能成为下一个最大值的元素下标。因此这些下标按照从小到大的顺序被存储,并且它们对应的值是严格单调递减的。时间复杂度 \(O(n)\),空间复杂度 \(O(k)\)

如果队列中有两个下标,其对应的值相等或递增,后者一定比前者存在的时间更久,因此前者不可能成为最大值,可以弹出。

因此当窗口右侧进入新元素时,要先弹出比之小的所有元素。而窗口左侧的元素则在离开窗口时就可弹出。两侧都需要弹出元素,因此使用双端队列

962. 最大宽度坡 (M)

题目描述:给定一个整数数组,定义坡是元组 (i,j),其中 i<jA[i]<=A[j],此时坡的宽度为 j-i。求坡的最大宽度。

方法1:贪心 + 单调队列 + 二分,能成为最长子数组的左端点的元素必然构成一个递减序列,因为如果来了一个大于等于栈顶的元素,则栈顶元素一定能比新元素构成更长的区间。先正向遍历获得单调队列,再枚举每个点作为右端点,二分查找第一个满足 A[i]<=A[j] 的左端点,时间复杂度 \(O(n\log n)\)

方法2:贪心 + 单调队列 + 栈,上述单调队列用栈实现。先正向遍历获得单调递减栈,再反向遍历枚举右端点,每遇到比栈顶更大的元素就更新答案并弹出元素,因为不会再用到。时间复杂度 \(O(n)\)

排序贪心

排序贪心问题通常涉及一组任务、事件或对象,需要按照某种顺序排列,目标是优化某个全局指标(如总时间、总成本、总收益等)。其核心解法是确定一个局部最优的选择顺序,最终达到全局最优。

因此,需要找到对象 A 排在对象 B 前的充分必要条件,并证明这个条件具有贪心选择性。

原创. 排队接水 (E)

题目描述:有 \(n\) 个人在一个水龙头前排队接水,数组 times 表示每个人接水所需时间,安排一个顺序使得所有人的等待时间总和最小。

直觉:让时间短的人先接水,可以减少后面人的等待时间。

证明:对于任意相邻的两个人 \(t_i<t_j\),他们的顺序不会影响前面和后面人的等待时间。如果 \(i\) 排在 \(j\) 前,则两人的等待时间为 \(t_i+(t_i+t_j)\),反之则为 \(t_j+(t_j+t_i)\),显然前者更小,因此要让更小者排在前面。

方法:排序 + 贪心,按照接水时间从小到大排序,累计前缀和即可。时间复杂度 \(O(n\log n)\)

原创. 打怪兽 (M)

题目描述:有 \(n\) 个怪兽,每个怪兽有自己的血量 HP 和它的攻击力 DPS。你可以选择其中一只,在挨了所有存活怪兽的一次攻击后攻击它。你只有 1 点攻击力,求最少会受到多少伤害。

方法:排序 + 贪心,除了要考虑到会被一只怪物打 \(DPS \times HP\) 的伤害,还要考虑到被剩余所有怪物打 \(HP\) 下,因此需要排序来减少剩余怪物的总伤害。此外,本题还有个隐含线索,就是当选中一只怪物,就必须打到底。所以就是一个贪心排序问题。时间复杂度 \(O(n\log n)\)

直觉 1:先打 DPS 高的怪兽。反例:一个怪兽 HP 1 DPS 99,另一个怪兽 HP 100 DPS 100。如先打后者,就会被前者一直打很久。

直觉 2:先打 DPS / HP 高的怪兽。

证明:对于任意的两个相邻的怪兽 \(i\)\(j\),他们的顺序不会影响前面和后面的伤害。如果先打 \(i\) 则会受到: \[ DPS[i]\times HP[i] + DPS[j]\times (HP[i]+ HP[j]) \] 反之如果先打 \(j\) 则会受到: \[ DPS[j]\times HP[j] + DPS[i]\times (HP[i]+ HP[j]) \] 如果 \(i\) 要排在前面,则上式要小于下式,则有: \[ DPS[j] \times HP [i] < DPS[i] \times HP[j] \] 自定义排序:return i.dps * j.hp < j.dps * i.hp;

56. 合并区间 (M)

题目描述:给定 N 个数对表示若干个区间,将所有重叠的区间合并为一个大区间,返回合并后的数对集合。

方法:排序 + 贪心,将区间按照左端点排序,维护一个当前的 \(start\)\(end\),如果下一个区间左端点大于 \(end\),则另起一个大区间;否则将其合并,更新 \(end\) 即可。 时间复杂度 \(O(n\log n)\)

646. 最长数对链 (活动安排问题) (M)

题目描述:N 个数对(第一个数字总是比第二个数字小)中,选择部分构造数对链,使得 (a,b)->(c,d) 满足 b<c。找出并返回能够形成的最长数对链的长度

方法1:当成 LIS 问题,也是要找一个递增序列,有 DP 和贪心 + 二分查找解法,复杂度 \(O(n^2)\)\(O(n \log n)\)

方法2:排序 + 贪心,优先挑选第二个数字最小的,这样能给挑选后续的数对留下更多的空间。因此按照第二个数字排序,排序复杂度 \(O(n \log n)\),再遍历一遍即可。

870. 优势洗牌 (M)

题目描述:给定两个大小相等的数组 nums1nums2,如果 nums1 中的数大于 nums2相同位置的数,则具有优势,返回 num1一个排列,使其优势最大化。

方法1:贪心 + multiset,每次在 nums1 中寻找大于 nums2[i]最小值;若没有,则返回 nums1 中的最小值。为了防止重复使用,每次要在 nums1删除该数字且保持有序,因此采用 multiset,时间复杂度 \(O(n\log n)\)

方法2:贪心 + 索引排序 + 对撞双指针,将两个数组都进行索引排序。每次取首个元素,如果前者大于后者,则进行配对;如果不大于,则前者和 nums2最大数进行配对,用双指针指向 nums2 的首尾。时间复杂度 \(O(n\log n)\)

\(nums1\) 可以改变原有的顺序,因此可以直接在其上进行排序,不需要索引化。

\(nums2\) 不能改变原有的顺序(否则就没法对应放置数字),只能新建一个 \(idx\) 数组并初始化为索引序列,再自定义排序函数实现映射:

1
2
3
vector<int> idx(n);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int i, int j){ return nums[i] < nums[j]; });

之后就可以通过 nums2[idx[i]] 来访问升序的数组,答案也可以直接放在 nums2

坑点:方法 1 中如果不采用 multiset 而是用排序的数组,每次删除操作的复杂度是 \(O(n)\),整体复杂度就是 \(O(n^2)\)

406. 根据身高重建队列 (M)

题目描述:有打乱顺序的一群人站成一个队列,每人提供两个属性:他的身高、他前面应该有多少个身高大于等于他的人。要求将这群人排回原来的顺序

直觉:矮个子排在哪都对高个子没有影响,但是高个子排在矮个子前面就会造成影响。所以,高个子可以先排,矮个子再插队。因此要先按身高从大到小排序,身高相同再按第二关键字从小到大排序。

自定义排序:return u[0] > v[0] || (u[0] == v[0] && u[1] < v[1]);

方法:自定义排序 + 贪心,遍历排序后的数组,后来的矮个子直接插入到第二关键字的位置,能满足自身属性且不会影响到之前的队列属性,时间复杂度 \(O(n^2)\)

2449. 使数组相似的最少操作次数 (H)

题目描述:给定长度相等的两个正整数数组 numstarget,操作 nums,使其与 target 中每个元素出现次数相等,但位置可以不同。每次操作需选中两个数,其中一个数 \(+2\),另一个数 \(-2\)。计算最少操作次数。

方法:排序 + 贪心,要使操作次数最小化,可以证明应该让最小的一对、次小的一对、以此类推。由于 \(\pm 2\) 不会改变奇偶性,因此配对时考虑奇偶数分离,再进行排序(由于原数组是正数,可以考虑将奇数翻转为负来分离)。累加每对元素的差的绝对值,时间复杂度 \(O(n\log n)\)

坑点:本题保证能使两个数组相似,因此最终累加的结果除以 \(4\) 一定能得到整数。


力扣刷题笔记 #07 贪心算法
https://hwcoder.top/LeetCode-Greedy
作者
Wei He
发布于
2022年10月2日
许可协议