LeetCode 3347 执行操作后元素的最高频率 II候选值枚举 排序二分的完整题解力扣加加 LeetCode 解题之路【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本文是 leetcode 解题仓库LeetCode Solutions: A Record of My Problem Solving Journey中 3347. 执行操作后元素的最高频率 II 一题的深度展开。通过本文你将掌握如何把「可修改nums[i]至多numOperations次、每次加减不超过k」的优化问题转化为候选值枚举 排序后二分计数的套路并理解为什么候选值只需要nums[i]、nums[i] k、nums[i] - k三种而不需要枚举整个值域。这套「枚举边界突变点 区间计数」的方法是同类频率最大化题目的通用解。题目全景输入、约束与两个示例题目原题与示例完整继承如下题目描述来自原文档 problems/3347.maximum-frequency-of-an-element-after-performing-operations-ii.md给你一个整数数组nums和两个整数k和numOperations。你必须对nums执行numOperations次操作。每次操作中你可以选择一个下标i它在之前的操作中没有被选择过。将nums[i]增加范围[-k, k]中的一个整数。在执行完所有操作以后返回nums中出现频率最高元素的出现次数。一个元素x的频率指的是它在数组中出现的次数。示例 1输入nums [1,4,5], k 1, numOperations 2输出2解释通过以下操作得到最高频率 2将nums[1]增加 0nums变为[1, 4, 5]。将nums[2]增加 -1nums变为[1, 4, 4]。示例 2输入nums [5,11,20,20], k 5, numOperations 1输出2解释通过以下操作得到最高频率 2将nums[1]增加 0即不动保持原数组。提示数据范围约束约束项范围nums.length1 nums.length 10^5nums[i]1 nums[i] 10^9k0 k 10^9numOperations0 numOperations nums.length这些约束决定了算法方向n最大10^5且值域高达10^9因此任何基于值域枚举的暴力做法都会超时必须把候选值压缩到 O(n) 量级并用 O(n log n) 的排序 二分来完成。前置知识二分查找本题的计数环节依赖在有序数组上快速统计落在闭区间[x - k, x k]内的元素个数即bisect_left / bisect_right的应用。仓库的二分方法论专题thinkings/binary-search-2.md《几乎刷完了力扣所有的二分题我发现了这些东西下》系统讲解了二分的前提数组有序与常见变形本题正是在有序序列上做二分定位边界的典型应用。思路推导从朴素枚举到候选值压缩朴素枚举为什么不可行容易想到的思路是枚举最高频率的元素的值v统计nums中所有能通过不超过一次操作变成v的元素个数再结合numOperations限制取最大值。v一定介于数组最小值- k和最大值 k之间但这个值域跨度最大可达2 * 10^9逐值枚举必然超时。一个反直觉的事实候选值不一定是原数组元素初次尝试时很多人会认为v一定是nums中某个元素的值于是只枚举nums的元素。但这并不正确。原文档给出了一个关键反例nums [88, 53]k 27。把二者之一变成 88 或 53最高频率都只有 1而把 88 变成88 - 27 61可以让 53 和 61 之间距离为8 k二者都能变成 61最高频率变为 2。可见候选值必须额外包含nums[i] k与nums[i] - k——因为当两个元素的可变区间没有直接重叠到对方原值时需要折中到中间某个值才能让两者相等。数形结合把每个元素看作一条竖线原文档用数形结合的方式解释这一结论此处以文字还原其几何含义把nums中每个元素值画成一个黑色点每个点经过一次操作可以变成[nums[i] - k, nums[i] k]范围内的任意整数对应一条以该点为中心、长度2k的竖线。若两条竖线之间有红色重叠区域就可以通过一次操作让二者相等若二者本来就相等则无需操作。若一条竖线的端点恰好落在另一条竖线的覆盖范围内则可以把其中一个数直接变成另一个数。若两条竖线既不相交、端点也不落在对方范围内则无论如何无法通过一次操作使二者相等。接下来把枚举v想象成一条水平红线从低到高移动。可以发现红线的移动过程中只有在扫过nums[i]、nums[i] k、nums[i] - k这三个位置时区间计数即能变成v的元素个数才会发生突变。这是因为这些位置对应着某条竖线的端点或中心点是某个元素能否被纳入计数的临界点。因此我们只需要考虑这三类值而不是它们之间的所有整数——这就是把 O(值域) 压缩到 O(3n) 的关键。对每个候选值 v 的计数规则对于固定的候选值v统计nums中能通过至多一次操作变成v的元素个数若nums[i] v本身已经是目标值不需要操作若nums[i] - k v nums[i] k操作一次即可变成v计入可操作数量否则无法操作不计入。于是问题变成统计nums中落在闭区间[v - k, v k]内的元素个数并减去其中本来就等于v的个数。前者用排序 二分 O(log n) 得到后者用哈希计数CounterO(1) 得到。算法步骤用Counter(nums)统计每个值在原始数组中的出现次数mp。构造候选值集合st对每个x in nums加入x、x - k、x k。去重后候选值数量不超过3n。对nums排序以便二分计数。遍历st中的每个候选值xin_range bisect_right(nums, x k) - bisect_left(nums, x - k)闭区间[x - k, x k]内的元素总数except_self in_range - mp[x]其中可以通过一次操作变成x的元素个数排除原本就是x的它们不需要消耗操作次数能新增的频率不能超过numOperations故added min(except_self, numOperations)ans max(ans, mp[x] added)。返回ans。细节为什么except_self要min掉numOperationsexcept_self只是理论上能操作的元素个数但操作总次数被numOperations限制且每个下标只能被选择一次。即使有 100 个元素都能变成v若numOperations 2最多只能把其中 2 个真的改过去。所以最终答案的上界是mp[x] min(except_self, numOperations)。这也是示例 2 中明明有三个元素5、11、20可以汇聚到 20却因numOperations 1只能得到频率 2 的原因。代码实现Python3原文档的 Python3 解法如下problems/3347.maximum-frequency-of-an-element-after-performing-operations-ii.mdclass Solution: def maxFrequency(self, nums: List[int], k: int, numOperations: int) - int: # 把所有要考虑的值放进 set 里 st set() # 统计 nums 里每种数出现了几次 mp Counter(nums) for x in nums: st.add(x) st.add(x - k) st.add(x k) # 给 nums 排序方便接下来二分计数。 nums.sort() ans 0 for x in st: except_self ( bisect.bisect_right(nums, x k) - bisect.bisect_left(nums, x - k) - mp[x] ) ans max(ans, mp[x] min(except_self, numOperations)) return ans代码要点逐行解读候选值集合st之所以用set收集x、x - k、x k正是思路推导中红线突变点的落地——集合天然去重候选量级为 O(n)。bisect_left(nums, x - k)返回第一个 x - k的位置bisect_right(nums, x k)返回第一个 x k的位置两者之差即为闭区间[x - k, x k]内的元素个数完全对应计数规则中的nums[i] - k v nums[i] k。- mp[x]把本就不需要操作的x本身从可操作数量中剔除避免把x自身也算成一次操作x的自身出现次数已经通过mp[x]计入答案基数。最终mp[x] min(except_self, numOperations)保证原本频率 操作带来的增量且增量不越界。边界情况验证k 0操作只能增加 0即无法改变任何元素。此时区间[x, x]内只有等于x的元素except_self 0答案退化为max(Counter(nums).values())即原数组最大频率。numOperations 0没有任何操作可用min(except_self, 0) 0答案同样是原数组最大频率。所有元素相等如[5,5,5]mp[5] 3except_self为 0答案即3。复杂度分析令n为数组长度原文档的复杂度结论与此一致时间复杂度O(n log n)。排序O(n log n)候选值最多3n个每个候选值做两次二分查找O(log n)合计O(n log n)。空间复杂度O(n)。set候选集合与Counter哈希表在最坏情况下均达到 O(n) 量级。本题在仓库中的定位与延伸本题已收录于仓库题解列表可在 README.md3347. 执行操作后元素的最高频率 II与 SUMMARY.md 目录中找到入口。题目类型为排序 二分 区间计数的优化题与仓库二分专题 thinkings/binary-search-2.md 的方法论一脉相承先排序构造有序序列再用二分定位边界。同类频率/计数最大化题目可横向对比424. 替换后的最长重复字符同样是有限次修改 最大化某值频率但采用滑动窗口最长连续 1 模型解决895. 最大频率栈频率作为数据结构设计约束而非操作目标。若对二分边界bisect_leftvsbisect_right容易混淆可参考仓库 thinkings/binary-search-2.md 中的二分变形总结——本题中左闭右闭区间计数正是两种二分原语组合使用的标准场景。小结3347的核心套路可以一句话概括频率最大化问题不必枚举整个值域只需枚举每个元素及其可达区间端点作为候选目标值再用排序 二分快速统计每个候选值的可操作元素个数最后用numOperations封顶增量。掌握「候选值压缩边界突变点 二分区间计数」这一组合你就能举一反三地解决同类可达范围聚合类题目。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode 3347 执行操作后元素的最高频率 II：候选值枚举 + 排序二分的完整题解（力扣加加 LeetCode 解题之路）
LeetCode 3347 执行操作后元素的最高频率 II候选值枚举 排序二分的完整题解力扣加加 LeetCode 解题之路【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本文是 leetcode 解题仓库LeetCode Solutions: A Record of My Problem Solving Journey中 3347. 执行操作后元素的最高频率 II 一题的深度展开。通过本文你将掌握如何把「可修改nums[i]至多numOperations次、每次加减不超过k」的优化问题转化为候选值枚举 排序后二分计数的套路并理解为什么候选值只需要nums[i]、nums[i] k、nums[i] - k三种而不需要枚举整个值域。这套「枚举边界突变点 区间计数」的方法是同类频率最大化题目的通用解。题目全景输入、约束与两个示例题目原题与示例完整继承如下题目描述来自原文档 problems/3347.maximum-frequency-of-an-element-after-performing-operations-ii.md给你一个整数数组nums和两个整数k和numOperations。你必须对nums执行numOperations次操作。每次操作中你可以选择一个下标i它在之前的操作中没有被选择过。将nums[i]增加范围[-k, k]中的一个整数。在执行完所有操作以后返回nums中出现频率最高元素的出现次数。一个元素x的频率指的是它在数组中出现的次数。示例 1输入nums [1,4,5], k 1, numOperations 2输出2解释通过以下操作得到最高频率 2将nums[1]增加 0nums变为[1, 4, 5]。将nums[2]增加 -1nums变为[1, 4, 4]。示例 2输入nums [5,11,20,20], k 5, numOperations 1输出2解释通过以下操作得到最高频率 2将nums[1]增加 0即不动保持原数组。提示数据范围约束约束项范围nums.length1 nums.length 10^5nums[i]1 nums[i] 10^9k0 k 10^9numOperations0 numOperations nums.length这些约束决定了算法方向n最大10^5且值域高达10^9因此任何基于值域枚举的暴力做法都会超时必须把候选值压缩到 O(n) 量级并用 O(n log n) 的排序 二分来完成。前置知识二分查找本题的计数环节依赖在有序数组上快速统计落在闭区间[x - k, x k]内的元素个数即bisect_left / bisect_right的应用。仓库的二分方法论专题thinkings/binary-search-2.md《几乎刷完了力扣所有的二分题我发现了这些东西下》系统讲解了二分的前提数组有序与常见变形本题正是在有序序列上做二分定位边界的典型应用。思路推导从朴素枚举到候选值压缩朴素枚举为什么不可行容易想到的思路是枚举最高频率的元素的值v统计nums中所有能通过不超过一次操作变成v的元素个数再结合numOperations限制取最大值。v一定介于数组最小值- k和最大值 k之间但这个值域跨度最大可达2 * 10^9逐值枚举必然超时。一个反直觉的事实候选值不一定是原数组元素初次尝试时很多人会认为v一定是nums中某个元素的值于是只枚举nums的元素。但这并不正确。原文档给出了一个关键反例nums [88, 53]k 27。把二者之一变成 88 或 53最高频率都只有 1而把 88 变成88 - 27 61可以让 53 和 61 之间距离为8 k二者都能变成 61最高频率变为 2。可见候选值必须额外包含nums[i] k与nums[i] - k——因为当两个元素的可变区间没有直接重叠到对方原值时需要折中到中间某个值才能让两者相等。数形结合把每个元素看作一条竖线原文档用数形结合的方式解释这一结论此处以文字还原其几何含义把nums中每个元素值画成一个黑色点每个点经过一次操作可以变成[nums[i] - k, nums[i] k]范围内的任意整数对应一条以该点为中心、长度2k的竖线。若两条竖线之间有红色重叠区域就可以通过一次操作让二者相等若二者本来就相等则无需操作。若一条竖线的端点恰好落在另一条竖线的覆盖范围内则可以把其中一个数直接变成另一个数。若两条竖线既不相交、端点也不落在对方范围内则无论如何无法通过一次操作使二者相等。接下来把枚举v想象成一条水平红线从低到高移动。可以发现红线的移动过程中只有在扫过nums[i]、nums[i] k、nums[i] - k这三个位置时区间计数即能变成v的元素个数才会发生突变。这是因为这些位置对应着某条竖线的端点或中心点是某个元素能否被纳入计数的临界点。因此我们只需要考虑这三类值而不是它们之间的所有整数——这就是把 O(值域) 压缩到 O(3n) 的关键。对每个候选值 v 的计数规则对于固定的候选值v统计nums中能通过至多一次操作变成v的元素个数若nums[i] v本身已经是目标值不需要操作若nums[i] - k v nums[i] k操作一次即可变成v计入可操作数量否则无法操作不计入。于是问题变成统计nums中落在闭区间[v - k, v k]内的元素个数并减去其中本来就等于v的个数。前者用排序 二分 O(log n) 得到后者用哈希计数CounterO(1) 得到。算法步骤用Counter(nums)统计每个值在原始数组中的出现次数mp。构造候选值集合st对每个x in nums加入x、x - k、x k。去重后候选值数量不超过3n。对nums排序以便二分计数。遍历st中的每个候选值xin_range bisect_right(nums, x k) - bisect_left(nums, x - k)闭区间[x - k, x k]内的元素总数except_self in_range - mp[x]其中可以通过一次操作变成x的元素个数排除原本就是x的它们不需要消耗操作次数能新增的频率不能超过numOperations故added min(except_self, numOperations)ans max(ans, mp[x] added)。返回ans。细节为什么except_self要min掉numOperationsexcept_self只是理论上能操作的元素个数但操作总次数被numOperations限制且每个下标只能被选择一次。即使有 100 个元素都能变成v若numOperations 2最多只能把其中 2 个真的改过去。所以最终答案的上界是mp[x] min(except_self, numOperations)。这也是示例 2 中明明有三个元素5、11、20可以汇聚到 20却因numOperations 1只能得到频率 2 的原因。代码实现Python3原文档的 Python3 解法如下problems/3347.maximum-frequency-of-an-element-after-performing-operations-ii.mdclass Solution: def maxFrequency(self, nums: List[int], k: int, numOperations: int) - int: # 把所有要考虑的值放进 set 里 st set() # 统计 nums 里每种数出现了几次 mp Counter(nums) for x in nums: st.add(x) st.add(x - k) st.add(x k) # 给 nums 排序方便接下来二分计数。 nums.sort() ans 0 for x in st: except_self ( bisect.bisect_right(nums, x k) - bisect.bisect_left(nums, x - k) - mp[x] ) ans max(ans, mp[x] min(except_self, numOperations)) return ans代码要点逐行解读候选值集合st之所以用set收集x、x - k、x k正是思路推导中红线突变点的落地——集合天然去重候选量级为 O(n)。bisect_left(nums, x - k)返回第一个 x - k的位置bisect_right(nums, x k)返回第一个 x k的位置两者之差即为闭区间[x - k, x k]内的元素个数完全对应计数规则中的nums[i] - k v nums[i] k。- mp[x]把本就不需要操作的x本身从可操作数量中剔除避免把x自身也算成一次操作x的自身出现次数已经通过mp[x]计入答案基数。最终mp[x] min(except_self, numOperations)保证原本频率 操作带来的增量且增量不越界。边界情况验证k 0操作只能增加 0即无法改变任何元素。此时区间[x, x]内只有等于x的元素except_self 0答案退化为max(Counter(nums).values())即原数组最大频率。numOperations 0没有任何操作可用min(except_self, 0) 0答案同样是原数组最大频率。所有元素相等如[5,5,5]mp[5] 3except_self为 0答案即3。复杂度分析令n为数组长度原文档的复杂度结论与此一致时间复杂度O(n log n)。排序O(n log n)候选值最多3n个每个候选值做两次二分查找O(log n)合计O(n log n)。空间复杂度O(n)。set候选集合与Counter哈希表在最坏情况下均达到 O(n) 量级。本题在仓库中的定位与延伸本题已收录于仓库题解列表可在 README.md3347. 执行操作后元素的最高频率 II与 SUMMARY.md 目录中找到入口。题目类型为排序 二分 区间计数的优化题与仓库二分专题 thinkings/binary-search-2.md 的方法论一脉相承先排序构造有序序列再用二分定位边界。同类频率/计数最大化题目可横向对比424. 替换后的最长重复字符同样是有限次修改 最大化某值频率但采用滑动窗口最长连续 1 模型解决895. 最大频率栈频率作为数据结构设计约束而非操作目标。若对二分边界bisect_leftvsbisect_right容易混淆可参考仓库 thinkings/binary-search-2.md 中的二分变形总结——本题中左闭右闭区间计数正是两种二分原语组合使用的标准场景。小结3347的核心套路可以一句话概括频率最大化问题不必枚举整个值域只需枚举每个元素及其可达区间端点作为候选目标值再用排序 二分快速统计每个候选值的可操作元素个数最后用numOperations封顶增量。掌握「候选值压缩边界突变点 二分区间计数」这一组合你就能举一反三地解决同类可达范围聚合类题目。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考