使数组成为等数数组的最小代价

标签: 贪心 数组 数学 排序

难度: Medium

给你一个长度为 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 <= 105
  • 1 <= nums[i] <= 109

Submission

运行时间: 87 ms

内存: 30.4 MB

class Solution:
    def minimumCost(self, nums: List[int]) -> int:
        nums.sort()
        l = len(nums)

        def bigger(x):
            x = str(x)
            n = len(x)
            k = n // 2

            if n % 2:
                y = x[:k + 1] + x[:k][::-1]
                if y >= x:
                    return int(y)
                else:
                    cur = int(x[:k+1]) + 1
                    return int(str(cur) + str(cur)[:-1][::-1]) if len(str(cur)) == k + 1 else int(str(cur) + str(cur)[:-2][::-1])
            
            else:
                y = x[:k] + x[:k][::-1]
                if y >= x:
                    return int(y)
                else:
                    cur = int(x[:k]) + 1
                    return int(str(cur) + str(cur)[::-1]) if len(str(cur)) == k else int(str(cur) + str(cur)[:-1][::-1])
            
        def smaller(x):
            x = str(x)
            n = len(x)
            k = n // 2

            if n % 2:
                y = x[:k + 1] + x[:k][::-1]
                if y <= x:
                    return int(y)
                else:
                    cur = int(x[:k+1]) - 1
                    return int(str(cur) + str(cur)[:-1][::-1]) if len(str(cur)) == k + 1 else int(str(cur) + str(cur)[::-1])
            
            else:
                y = x[:k] + x[:k][::-1]
                if y <= x:
                    return int(y)
                else:
                    cur = int(x[:k]) - 1
                    return int(str(cur) + str(cur)[::-1]) if len(str(cur)) == k and cur else int(str(cur) + '9' + str(cur)[::-1])*(cur!=0)+9*(cur == 0)
        
        a = smaller(nums[l//2])        
        b = bigger(nums[(l - 1)//2])
        return min(sum(abs(b-x) for x in nums), sum(abs(a-x) for x in nums))

Explain

此题解首先对数组进行排序，从而简化找到最佳回文数目标值的过程。利用中位数或接近中位数的值作为可能的目标回文数是一个高效的策略，因为中位数附近的值在优化总距离和上是很有帮助的。接着，题解定义了两个辅助函数 bigger 和 smaller 来计算给定数值的最近大回文数和最近小回文数。这些函数通过字符串操作检查并构造回文数。最后，题解通过计算将所有数组元素变为这两个回文数（由中位数计算得到）的代价，并返回较小的一个，从而实现了找到最小总代价的目标。

时间复杂度: O(n log n)

空间复杂度: O(1)

class Solution:
    def minimumCost(self, nums: List[int]) -> int:
        nums.sort()  # 对数组进行排序
        l = len(nums)

        def bigger(x):
            x = str(x)
            n = len(x)
            k = n // 2

            if n % 2:  # 奇数长度的数处理
                y = x[:k + 1] + x[:k][::-1]
                if y >= x:
                    return int(y)
                else:
                    cur = int(x[:k+1]) + 1
                    return int(str(cur) + str(cur)[:-1][::-1]) if len(str(cur)) == k + 1 else int(str(cur) + str(cur)[:-2][::-1])
            else:  # 偶数长度的数处理
                y = x[:k] + x[:k][::-1]
                if y >= x:
                    return int(y)
                else:
                    cur = int(x[:k]) + 1
                    return int(str(cur) + str(cur)[::-1]) if len(str(cur)) == k else int(str(cur) + str(cur)[:-1][::-1])
        
        def smaller(x):
            x = str(x)
            n = len(x)
            k = n // 2

            if n % 2:
                y = x[:k + 1] + x[:k][::-1]
                if y <= x:
                    return int(y)
                else:
                    cur = int(x[:k+1]) - 1
                    return int(str(cur) + str(cur)[:-1][::-1]) if len(str(cur)) == k + 1 else int(str(cur) + str(cur)[::-1])
            else:
                y = x[:k] + x[:k][::-1]
                if y <= x:
                    return int(y)
                else:
                    cur = int(x[:k]) - 1
                    return int(str(cur) + str(cur)[::-1]) if len(str(cur)) == k and cur else int(str(cur) + '9' + str(cur)[::-1])*(cur!=0)+9*(cur == 0)
        
        a = smaller(nums[l//2])  # 计算最小的回文数
        b = bigger(nums[(l - 1)//2])  # 计算最大的回文数
        return min(sum(abs(b-x) for x in nums), sum(abs(a-x) for x in nums))  # 计算最小总代价并返回

Explore

在优化整体代价的问题中，使用中位数作为目标值可以最小化所有元素与此目标的绝对差值的总和。相对于平均数，中位数对异常值不敏感，因此能更好地表示数据的中心趋势，特别是在需要考虑距离和时。在本题中，我们的目标是将所有数转换为回文数，而选择中位数附近的数作为目标回文数可以有效减少转换的总代价，因为中位数本身就处于数组的中间位置，从而使得总距离最小化。

在`bigger`和`smaller`函数中，通过构造回文数后，会进行比较以确保生成的回文数是大于或小于原始数字的最接近的回文数。如果构造出的回文数不符合要求（例如，不是最接近的大回文数或小回文数），则调整中间部分的数字（增大或减小），再重新构造回文数进行比较。这种方法通过直接构造并调整来确保结果是最接近的大回文数或小回文数。这种策略确保了构造的回文数既符合大小要求，也是距离最近的有效回文数。

即使在所有数值都是极小值或极大值的边界情况下，基于中位数的方法仍然有效。中位数的定义本质上是排序后位于中间的数值，因此无论数组中的数值如何极端，中位数总是有效地反映了数组的中心位置。在这种情况下，将数组中的数转换为基于中位数的回文数可能依然是最优解，因为这样的转换总体上确保了最小的代价。但是，需要注意的是，如果所有数值极端相同，转换成任何一个回文数的成本都会是一样的，因此这种情况下选择哪一个回文数将不会影响总代价。