LeetCode 题解工作台
使数组成为等数数组的最小代价
给你一个长度为 n 下标从 0 开始的整数数组 nums 。 你可以对 nums 执行特殊操作 任意次 （也可以 0 次）。每一次特殊操作中，你需要 按顺序 执行以下步骤： 从范围 [0, n - 1] 里选择一个下标 i 和一个 正 整数 x 。 将 |nums[i] - x| 添加到总代价里。 …
5
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·搜索·答案·空间
答案摘要
题目中回文数的范围是 $[1, 10^9]$，回文数由于对称性，我们可以在 $[1, 10^5]$ 的范围内枚举，然后将其翻转后拼接，得到所有的回文数，注意，如果是奇数长度的回文数，我们在翻转前要去掉最后一位。预处理得到的回文数数组记为 。我们对数组 进行排序。 接下来，我们对数组 进行排序，然后取 的中位数 ，我们只需要通过二分查找，在回文数组 中，找到一个与 最接近的数，然后计算 …
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个长度为 n 下标从 0 开始的整数数组 nums 。
你可以对 nums 执行特殊操作 任意次 （也可以 0 次）。每一次特殊操作中，你需要 按顺序 执行以下步骤：
- 从范围
[0, n - 1]里选择一个下标i和一个 正 整数x。 - 将
|nums[i] - x|添加到总代价里。 - 将
nums[i]变为x。
如果一个正整数正着读和反着读都相同，那么我们称这个数是 回文数 。比方说，121 ，2552 和 65756 都是回文数，但是 24 ，46 ，235 都不是回文数。
如果一个数组中的所有元素都等于一个整数 y ，且 y 是一个小于 109 的 回文数 ，那么我们称这个数组是一个 等数数组 。
请你返回一个整数，表示执行任意次特殊操作后使 nums 成为 等数数组 的 最小 总代价。
示例 1：
输入：nums = [1,2,3,4,5] 输出：6 解释：我们可以将数组中所有元素变为回文数 3 得到等数数组，数组变成 [3,3,3,3,3] 需要执行 4 次特殊操作，代价为 |1 - 3| + |2 - 3| + |4 - 3| + |5 - 3| = 6 。 将所有元素变为其他回文数的总代价都大于 6 。
示例 2：
输入：nums = [10,12,13,14,15] 输出：11 解释：我们可以将数组中所有元素变为回文数 11 得到等数数组，数组变成 [11,11,11,11,11] 需要执行 5 次特殊操作，代价为 |10 - 11| + |12 - 11| + |13 - 11| + |14 - 11| + |15 - 11| = 11 。 将所有元素变为其他回文数的总代价都大于 11 。
示例 3 ：
输入：nums = [22,33,22,33,22] 输出：22 解释：我们可以将数组中所有元素变为回文数 22 得到等数数组，数组变为 [22,22,22,22,22] 需要执行 2 次特殊操作，代价为 |33 - 22| + |33 - 22| = 22 。 将所有元素变为其他回文数的总代价都大于 22 。
提示：
1 <= n <= 1051 <= nums[i] <= 109
解题思路
方法一：预处理 + 排序 + 二分查找
题目中回文数的范围是 ，回文数由于对称性，我们可以在 的范围内枚举，然后将其翻转后拼接，得到所有的回文数，注意，如果是奇数长度的回文数，我们在翻转前要去掉最后一位。预处理得到的回文数数组记为 。我们对数组 进行排序。
接下来，我们对数组 进行排序，然后取 的中位数 ，我们只需要通过二分查找，在回文数组 中，找到一个与 最接近的数，然后计算 变成这个数的代价，即可得到答案。
时间复杂度 ，空间复杂度 。其中 是数组 的长度，而 是回文数组 的长度。
相似题目：
ps = []
for i in range(1, 10**5 + 1):
s = str(i)
t1 = s[::-1]
t2 = s[:-1][::-1]
ps.append(int(s + t1))
ps.append(int(s + t2))
ps.sort()
class Solution:
def minimumCost(self, nums: List[int]) -> int:
def f(x: int) -> int:
return sum(abs(v - x) for v in nums)
nums.sort()
i = bisect_left(ps, nums[len(nums) // 2])
return min(f(ps[j]) for j in range(i - 1, i + 2) if 0 <= j < len(ps))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is dominated by sorting the array O(n log n) and evaluating candidate palindromic numbers, which can be bounded by O(log(max(nums)) * n). Space complexity depends on storing candidates, usually O(n) or less. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Focus on array median and its relation to minimizing total distance.
- question_mark
Recognize the palindromic constraint restricts valid target numbers.
- question_mark
Binary search over the answer space is expected for efficiency.
常见陷阱
外企场景- error
Ignoring that the optimal target must be palindromic and choosing any median value.
- error
Recomputing costs from scratch for each candidate instead of using cumulative sums or efficient methods.
- error
Not considering edge cases where multiple palindromic numbers yield the same minimal cost.
进阶变体
外企场景- arrow_right_alt
Allow changing elements to any number, removing the palindromic restriction, which simplifies to standard median minimization.
- arrow_right_alt
Compute the minimum cost when only a limited number of special moves are allowed.
- arrow_right_alt
Consider arrays where elements are initially palindromic and only some need adjustment.