Leetcode 2967. Minimum Cost to Make Array Equalindromic

• Leetcode 2967. Minimum Cost to Make Array Equalindromic
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：2967. Minimum Cost to Make Array Equalindromic

1. 解题思路

这一题其实我的思路有点笨，多少有点暴力求解的意思。

显然，如果我们给出全部的对称数并将其有序排列，那么对于其中每一个对称数作为目标值时的cost就是一个包含一个最小值的先减后增有序数列，而我们要做的就是求这个最小值。

而对于任意一个对称数，我们可以通过二分查找在$O(logN)$的时间复杂度内找到原数组当中有多少数比他多，多少数比他少，然后通过累计数组可以直接获得对应的cost。

这些其实都还好，只是原则上感觉对于第一部分，对于这么有规律的东西应该有更好的算法可以更快找到最小值的，不过这里我暂时没想到，就直接遍历寻找了，所以感觉多少有点蠢了……

2. 代码实现

给出python代码实现如下：

@lru_cache(None)
def get_palindromes():ans = [0]for i in range(1, 10**6):s = str(i)a = int(s + s[::-1])if a <= 10**9:ans.append(a)b = int(s + s[:-1][::-1])if b <= 10**9:ans.append(b)return sorted(ans)class Solution:def minimumCost(self, nums: List[int]) -> int:n = len(nums)nums = sorted(nums)sums = [0] + list(accumulate(nums))palindromes = get_palindromes()ans = sums[-1]for x in palindromes:idx = bisect.bisect_right(nums, x)s = x * idx - (sums[idx] - sums[0]) + (sums[-1] - sums[idx]) - x * (n-idx)if ans >= s:ans = selse:breakreturn ans

提交代码评测得到：耗时2414ms，占用内存35.7MB。