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

简介: leetcode2967. 使数组成为等数数组的最小代价

题目

给你一个长度为 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

Problem: 100151. 使数组成为等数数组的最小代价

思路

找到整个数组中的中位数,找到这个中位数左右的第一个回文数,计算这两个回文数对于所有值的距离,返回相对比较小的那个

复杂度

时间复杂度:

主要是排耗时 O(nlogn)

空间复杂度:

只用到了常量,所以是 O(1)

Code

class Solution:
    def minimumCost(self, nums: List[int]) -> int:
        nums = sorted(nums)
        if len(nums)%2==1:
            midval1 = nums[len(nums)//2]
        else:
            midval1 = (nums[len(nums)//2] + nums[ len(nums)//2 -1 ]) // 2
        def check(num):
            num = str(num)
            left,right = 0,len(num)-1
            while left < right:
                if num[left] != num[right]:
                    return False
                left += 1
                right -=1
            return True
        
        def find(midval):
            if check(midval):
                return [midval,-1]
            left = midval-1
            right = midval+1
            while True:
                if check(left):
                    break
                left-=1
            while True:
                if check(right):
                    break
                right+=1
            return [left,right]
        s1 = find(midval1)
        a,b = s1[0],s1[1]
        ans1 = 0
        ans2 = 0
        for num in nums:
            ans1 += abs(a - num)
            ans2 += abs(b - num)
        return min(ans1,ans2)


目录
相关文章
|
4天前
|
算法
【数组相关面试题】LeetCode试题
【数组相关面试题】LeetCode试题
|
4天前
|
存储
力扣面试经典题之数组/字符串
力扣面试经典题之数组/字符串
27 0
|
4天前
|
人工智能 BI
力扣561 数组拆分
力扣561 数组拆分
|
4天前
【Leetcode】两数之和,给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
【Leetcode】两数之和,给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
|
4天前
|
算法
leetcode代码记录(寻找两个正序数组的中位数
leetcode代码记录(寻找两个正序数组的中位数
13 2
|
4天前
|
索引
leetcode代码记录(最长重复子数组
leetcode代码记录(最长重复子数组
12 0
|
4天前
leetcode代码记录(两个数组的交集
leetcode代码记录(两个数组的交集
9 1
|
4天前
leetcode代码记录(最大子数组和
leetcode代码记录(最大子数组和
11 2
|
4天前
|
存储 算法
Leetcode 30天高效刷数据结构和算法 Day1 两数之和 —— 无序数组
给定一个无序整数数组和目标值,找出数组中和为目标值的两个数的下标。要求不重复且可按任意顺序返回。示例:输入nums = [2,7,11,15], target = 9,输出[0,1]。暴力解法时间复杂度O(n²),优化解法利用哈希表实现,时间复杂度O(n)。
22 0
|
4天前
|
索引
Leetcode 给定一个数组,给定一个数字。返回数组中可以相加得到指定数字的两个索引
Leetcode 给定一个数组,给定一个数字。返回数组中可以相加得到指定数字的两个索引