LeetCode 题解工作台
使差值相等的最少数组改动次数
给你一个长度为 n 的整数数组 nums ， n 是 偶数 ，同时给你一个整数 k 。 你可以对数组进行一些操作。每次操作中，你可以将数组中 任一 元素替换为 0 到 k 之间的 任一 整数。 执行完所有操作以后，你需要确保最后得到的数组满足以下条件： 存在一个整数 X ，满足对于所有的 (0 都有…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
假设最终的数组中，数对 和 的差值为 。 我们不妨设 为 和 的较小值，设 为 和 的较大值。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个长度为 n 的整数数组 nums ，n 是 偶数 ，同时给你一个整数 k 。
你可以对数组进行一些操作。每次操作中，你可以将数组中 任一 元素替换为 0 到 k 之间的 任一 整数。
执行完所有操作以后，你需要确保最后得到的数组满足以下条件：
- 存在一个整数
X，满足对于所有的(0 <= i < n)都有abs(a[i] - a[n - i - 1]) = X。
请你返回满足以上条件 最少 修改次数。
示例 1：
输入：nums = [1,0,1,2,4,3], k = 4
输出：2
解释：
我们可以执行以下操作：
- 将
nums[1]变为 2 ，结果数组为nums = [1,2,1,2,4,3]。 - 将
nums[3]变为 3 ，结果数组为nums = [1,2,1,3,4,3]。
整数 X 为 2 。
示例 2：
输入：nums = [0,1,2,3,3,6,5,4], k = 6
输出：2
解释：
我们可以执行以下操作：
- 将
nums[3]变为 0 ，结果数组为nums = [0,1,2,0,3,6,5,4]。 - 将
nums[4]变为 4 ，结果数组为nums = [0,1,2,0,4,6,5,4]。
整数 X 为 4 。
提示：
2 <= n == nums.length <= 105n是偶数。0 <= nums[i] <= k <= 105
解题思路
方法一：差分数组
假设最终的数组中，数对 和 的差值为 。
我们不妨设 为 和 的较小值，设 为 和 的较大值。
对于每一对数，我们有以下几种情况：
- 如果不需要改动，那么 。
- 如果改动一次，那么 ，最大值就是把 变为 ，或者把 变为 。
- 如果改动两次，那么 。
即：
- 在 范围内，需要改动 次。
- 在 时，不需要改动。
- 在 范围内，需要改动 次。
- 在 范围内，需要改动 次。
我们枚举每一个数对，利用差分数组，更新每个数对在不同区间范围内的改动次数。
最后，我们求出差分数组的前缀和中的最小值，即为最少的改动次数。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
相似题目：
class Solution:
def minChanges(self, nums: List[int], k: int) -> int:
d = [0] * (k + 2)
n = len(nums)
for i in range(n // 2):
x, y = nums[i], nums[-i - 1]
if x > y:
x, y = y, x
d[0] += 1
d[y - x] -= 1
d[y - x + 1] += 1
d[max(y, k - x) + 1] -= 1
d[max(y, k - x) + 1] += 2
return min(accumulate(d))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate understands the importance of reducing the number of changes by focusing on the most frequent difference.
- question_mark
Candidate efficiently uses a hash table for counting occurrences and tracking differences between adjacent elements.
- question_mark
Candidate applies array scanning and hash lookup to solve the problem optimally, without over-complicating the solution.
常见陷阱
外企场景- error
Not recognizing the optimal way to handle the differences, leading to unnecessary changes.
- error
Failing to use a hash table effectively to count differences, which can slow down the solution.
- error
Over-complicating the problem by trying to handle all potential differences instead of focusing on the most frequent one.
进阶变体
外企场景- arrow_right_alt
What if the array length was not even, and you still needed to perform minimal changes?
- arrow_right_alt
How would the approach change if negative numbers were allowed in the array?
- arrow_right_alt
What if the range of possible replacements for each element was not fixed but varied?