Medium
题目描述
给你一个长度为 n 的 0 索引 整数数组 nums。
你可以对 nums 执行任意次数（包括零次）的 特殊操作。在一次特殊操作中，你需要按顺序执行以下步骤：
- 选择范围
[0, n - 1]内的一个索引i和一个正整数x。 - 将
|nums[i] - x|加到总代价中。 - 将
nums[i]的值更改为x。
回文数 是一个正整数，其数字反转后保持不变。例如，121、2552 和 65756 是回文数，而 24、46、235 不是回文数。
如果数组中的所有元素都等于一个整数 y，且 y 是一个小于 10^9 的回文数，则该数组被认为是 等回文数组。
返回通过执行任意次数的特殊操作使 nums 成为等回文数组的 最小可能总代价。
示例 1：
输入：nums = [1,2,3,4,5]
输出：6
解释：我们可以通过将所有元素更改为 3（回文数）来使数组成为等回文数组。使用 4 次特殊操作将数组更改为 [3,3,3,3,3] 的代价为 |1 - 3| + |2 - 3| + |4 - 3| + |5 - 3| = 6。
可以证明，将所有元素更改为除 3 以外的任何其他回文数都无法以更低的代价实现。
示例 2：
输入：nums = [10,12,13,14,15]
输出：11
解释：我们可以通过将所有元素更改为 11（回文数）来使数组成为等回文数组。使用 5 次特殊操作将数组更改为 [11,11,11,11,11] 的代价为 |10 - 11| + |12 - 11| + |13 - 11| + |14 - 11| + |15 - 11| = 11。
可以证明，将所有元素更改为除 11 以外的任何其他回文数都无法以更低的代价实现。
示例 3：
输入：nums = [22,33,22,33,22]
输出：22
解释：我们可以通过将所有元素更改为 22（回文数）来使数组成为等回文数组。使用 2 次特殊操作将数组更改为 [22,22,22,22,22] 的代价为 |33 - 22| + |33 - 22| = 22。
可以证明，将所有元素更改为除 22 以外的任何其他回文数都无法以更低的代价实现。
约束：
1 <= n <= 10^51 <= nums[i] <= 10^9
解题思路
解题思路
这道题的关键在于找到最优的回文数作为目标值。我们可以通过以下步骤来解决：
中位数特性：为了最小化所有元素到目标值的距离之和，最优的目标值应该接近数组的中位数。这是因为中位数能最小化到所有点的距离之和。
候选回文数：由于目标值必须是回文数，我们需要找到距离中位数最近的回文数。具体来说，我们需要考虑：
- 大于等于中位数的最小回文数
- 小于等于中位数的最大回文数
生成回文数：我们可以通过数学构造来生成这两个候选回文数：
- 对于一个数字，我们可以通过镜像其前半部分来构造回文数
- 如果构造的回文数小于原数，我们需要增加中间部分并重新构造
计算代价：对于每个候选回文数，计算将所有数组元素变为该值的总代价，取最小值。
算法流程：
- 排序数组并找到中位数
- 生成两个候选回文数（大于等于和小于等于中位数的）
- 计算每个候选的总代价
- 返回最小代价
推荐解法：数学构造法，时间复杂度更优。
代码实现
class Solution {
public:
long long minimumCost(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
int median = nums[n / 2];
// 获取小于等于median的最大回文数
long long lower = getLowerPalindrome(median);
// 获取大于等于median的最小回文数
long long upper = getUpperPalindrome(median);
return min(calculateCost(nums, lower), calculateCost(nums, upper));
}
private:
long long getLowerPalindrome(long long num) {
string s = to_string(num);
int n = s.length();
// 先构造镜像回文数
for (int i = 0; i < n / 2; i++) {
s[n - 1 - i] = s[i];
}
long long palindrome = stoll(s);
if (palindrome <= num) {
return palindrome;
}
// 如果镜像回文数大于原数，需要减小中间部分
if (n == 1) return num - 1;
// 减小前半部分
string half = s.substr(0, (n + 1) / 2);
long long halfNum = stoll(half) - 1;
if (halfNum == 0) return n == 1 ? 0 : 9;
string newHalf = to_string(halfNum);
if (newHalf.length() < half.length()) {
return stoll(string(n - 1, '9'));
}
string result = newHalf;
for (int i = n / 2 - 1; i >= 0; i--) {
result += newHalf[i];
}
return stoll(result);
}
long long getUpperPalindrome(long long num) {
string s = to_string(num);
int n = s.length();
// 先构造镜像回文数
for (int i = 0; i < n / 2; i++) {
s[n - 1 - i] = s[i];
}
long long palindrome = stoll(s);
if (palindrome >= num) {
return palindrome;
}
// 如果镜像回文数小于原数，需要增大中间部分
string half = s.substr(0, (n + 1) / 2);
long long halfNum = stoll(half) + 1;
string newHalf = to_string(halfNum);
if (newHalf.length() > half.length()) {
return stoll("1" + string(n - 1, '0') + "1");
}
string result = newHalf;
for (int i = n / 2 - 1; i >= 0; i--) {
result += newHalf[i];
}
return stoll(result);
}
long long calculateCost(const vector<int>& nums, long long target) {
long long cost = 0;
for (int num : nums) {
cost += abs(num - target);
}
return cost;
}
};
class Solution:
def minimumCost(self, nums: List[int]) -> int:
nums.sort()
n = len(nums)
median = nums[n // 2]
# 获取小于等于median的最大回文数
lower = self.get_lower_palindrome(median)
# 获取大于等于median的最小回文数
upper = self.get_upper_palindrome(median)
return min(self.calculate_cost(nums, lower), self.calculate_cost(nums, upper))
def get_lower_palindrome(self, num):
s = str(num)
n = len(s)
# 先构造镜像回文数
s_list = list(s)
for i in range(n // 2):
s_list[n - 1 - i] = s_list[i]
palindrome = int(''.join(s_list))
if palindrome <= num:
return palindrome
# 如果镜像回文数大于原数，需要减小中间部分
if n == 1:
return num - 1
# 减小前半部分
half = s[:(n + 1) // 2]
half_num = int(half) - 1
if half_num == 0:
return 9 if n == 1 else int('9' * (n - 1))
new_half = str(half_num)
if len(new_half) < len(half):
return int('9' * (n - 1))
result = new_half + new_half[n // 2 - 1::-1]
return int(result)
def get_upper_palindrome(self, num):
s = str(num)
n = len(s)
# 先构造镜像回文数
s_list = list(s)
for i in range(n // 2):
s_list[n - 1 - i] = s_list[i]
palindrome = int(''.join(s_list))
if palindrome >= num:
return palindrome
# 如果镜像回文数小于原数，需要增大中间部分
half = s[:(n + 1) // 2]
half_num = int(half) + 1
new_half = str(half_num)
if len(new_half) > len(half):
return int('1' + '0' * (n - 1) + '1')
result = new_half + new_half[n // 2 - 1::-1]
return int(result)
def calculate_cost(self, nums, target):
return sum(abs(num - target) for num in nums)
public class Solution {
public long MinimumCost(int[] nums) {
Array.Sort(nums);
int n = nums.Length;
long median = nums[n / 2];
// 获取小于等于median的最大回文数
long lower = GetLowerPalindrome(median);
// 获取大于等于median的最小回文数
long upper = GetUpperPalindrome(median);
return Math.Min(CalculateCost(nums, lower), CalculateCost(nums, upper));
}
private long GetLowerPalindrome(long num) {
string s = num.ToString();
int n = s.Length;
// 先构造镜像回文数
char[] chars = s.ToCharArray();
for (int i = 0; i < n / 2; i++) {
chars[n - 1 - i] = chars[i];
}
long palindrome = long.Parse(new string(chars));
if (palindrome <= num) {
return palindrome;
}
// 如果镜像回文数大于原数，需要减小中间部分
if (n == 1) return num - 1;
// 减小前半部分
string half = s.Substring(0, (n + 1) / 2);
long halfNum = long.Parse(half) - 1;
if (halfNum == 0) return n == 1 ? 0 : long.Parse(new string('9', n - 1));
string newHalf = halfNum.ToString();
if (newHalf.Length < half.Length) {
return long.Parse(new string('9', n - 1));
}
string result = newHalf;
for (int i = n / 2 - 1; i >= 0; i--) {
result += newHalf[i];
}
return long.Parse(result);
}
private long GetUpperPalindrome(long num) {
string s = num.ToString();
int n = s.Length;
// 先构造镜像回文数
char[] chars = s.ToCharArray();
for (int i = 0; i < n / 2; i++) {
chars[n - 1 - i] = chars[i];
}
long palindrome = long.Parse(new string(chars));
if (palindrome >= num) {
return palindrome;
}
// 如果镜像回文数小于原数，需要增大中间部分
string half = s.Substring(0, (n + 1) / 2);
long halfNum = long.Parse(half) + 1;
string newHalf = halfNum.ToString();
if (newHalf.Length > half.Length) {
return long.Parse("1" + new string('0', n - 1) + "1");
}
string result = newHalf;
for (int i = n / 2 - 1; i >= 0; i--) {
result += newHalf[i];
}
return long.Parse(result);
}
private long CalculateCost(int[] nums, long target) {
long cost = 0;
foreach (int num in nums) {
cost += Math.Abs(num - target);
}
return cost;
}
}
var minimumCost = function(nums) {
nums.sort((a, b) => a - b);
const n = nums.length;
const median = nums[Math.floor(n / 2)];
// 获取小于等于median的最大回文数
const lower = getLowerPalindrome(median);
// 获取大于等于median的最小回文数
const upper = getUpperPalindrome(median);
return Math.min(calculateCost(nums, lower), calculateCost(nums, upper));
复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间 | - |
| 空间 | - |