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

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

给你一个长度为 n 下标从 0 开始的整数数组 nums 。

你可以对 nums 执行特殊操作 任意次 （也可以 0 次）。每一次特殊操作中，你需要 按顺序 执行以下步骤：

从范围 [0, n - 1] 里选择一个下标 i 和一个正整数 x 。
将 |nums[i] - x| 添加到总代价里。
将 nums[i] 变为 x 。

如果一个正整数正着读和反着读都相同，那么我们称这个数是 回文数 。比方说，121 ，2552 和 65756 都是回文数，但是 24 ，46 ，235 都不是回文数。

如果一个数组中的所有元素都等于一个整数 y ，且 y 是一个小于 10⁹ 的 回文数 ，那么我们称这个数组是一个 等数数组 。

请你返回一个整数，表示执行任意次特殊操作后使 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 <= 10⁵
1 <= nums[i] <= 10⁹

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: long long minimumCost(vector<int>& nums) { } };

python3 解法, 执行用时: 164 ms, 内存消耗: 33.6 MB, 提交时间: 2023-12-17 23:35:49

'''
预处理回文数+中位数贪心
'''
# 严格按顺序从小到大生成所有回文数（不用字符串转换）
pal = []
base = 1
while base <= 10000:
    # 生成奇数长度回文数
    for i in range(base, base * 10):
        x = i
        t = i // 10
        while t:
            x = x * 10 + t % 10
            t //= 10
        pal.append(x)
    # 生成偶数长度回文数
    if base <= 1000:
        for i in range(base, base * 10):
            x = t = i
            while t:
                x = x * 10 + t % 10
                t //= 10
            pal.append(x)
    base *= 10
pal.append(1_000_000_001)  # 哨兵，防止下面代码中的 i 下标越界

class Solution:
    def minimumCost(self, nums: List[int]) -> int:
        # 注：排序只是为了找中位数，如果用快速选择算法，可以做到 O(n)
        nums.sort()

        # 返回 nums 中的所有数变成 pal[i] 的总代价
        def cost(i: int) -> int:
            target = pal[i]
            return sum(abs(x - target) for x in nums)

        n = len(nums)
        i = bisect_left(pal, nums[(n - 1) // 2])  # 二分找中位数右侧最近的回文数
        if pal[i] <= nums[n // 2]:  # 回文数在中位数范围内
            return cost(i)  # 直接变成 pal[i]
        return min(cost(i - 1), cost(i))  # 枚举离中位数最近的两个回文数 pal[i-1] 和 pal[i]

java 解法, 执行用时: 17 ms, 内存消耗: 55.1 MB, 提交时间: 2023-12-17 23:36:07

class Solution {
    private static final int[] pal = new int[109999];

    static {
        // 严格按顺序从小到大生成所有回文数（不用字符串转换）
        int palIdx = 0;
        for (int base = 1; base <= 10000; base *= 10) {
            // 生成奇数长度回文数
            for (int i = base; i < base * 10; i++) {
                int x = i;
                for (int t = i / 10; t > 0; t /= 10) {
                    x = x * 10 + t % 10;
                }
                pal[palIdx++] = x;
            }
            // 生成偶数长度回文数
            if (base <= 1000) {
                for (int i = base; i < base * 10; i++) {
                    int x = i;
                    for (int t = i; t > 0; t /= 10) {
                        x = x * 10 + t % 10;
                    }
                    pal[palIdx++] = x;
                }
            }
        }
        pal[palIdx++] = 1_000_000_001; // 哨兵，防止下面代码中的 i 下标越界
    }

    public long minimumCost(int[] nums) {
        // 注：排序只是为了找中位数，如果用快速选择算法，可以做到 O(n)
        Arrays.sort(nums);
        int n = nums.length;

        // 二分找中位数右侧最近的回文数
        int i = lowerBound(nums[(n - 1) / 2]);

        // 回文数在中位数范围内
        if (pal[i] <= nums[n / 2]) {
            return cost(nums, i); // 直接变成 pal[i]
        }

        // 枚举离中位数最近的两个回文数 pal[i-1] 和 pal[i]
        return Math.min(cost(nums, i - 1), cost(nums, i));
    }

    // 返回 nums 中的所有数变成 pal[i] 的总代价
    private long cost(int[] nums, int i) {
        int target = pal[i];
        long sum = 0;
        for (int x : nums) {
            sum += Math.abs(x - target);
        }
        return sum;
    }

    // 开区间写法
    private int lowerBound(int target) {
        int left = -1, right = pal.length; // 开区间 (left, right)
        while (left + 1 < right) { // 区间不为空
            // 循环不变量：
            // pal[left] < target
            // pal[right] >= target
            int mid = left + (right - left) / 2;
            if (pal[mid] < target)
                left = mid; // 范围缩小到 (mid, right)
            else
                right = mid; // 范围缩小到 (left, mid)
        }
        return right; // 或者 left+1
    }
}

golang 解法, 执行用时: 48 ms, 内存消耗: 9.1 MB, 提交时间: 2023-12-17 23:36:25

var pal = make([]int, 0, 109999)

func init() {
	// 按顺序从小到大生成所有回文数
	for base := 1; base <= 10000; base *= 10 {
		for i := base; i < base*10; i++ {
			x := i
			for t := i / 10; t > 0; t /= 10 {
				x = x*10 + t%10
			}
			pal = append(pal, x)
		}
		if base <= 1000 {
			for i := base; i < base*10; i++ {
				x := i
				for t := i; t > 0; t /= 10 {
					x = x*10 + t%10
				}
				pal = append(pal, x)
			}
		}
	}
	pal = append(pal, 1_000_000_001) // 哨兵，防止下标越界
}

func minimumCost(nums []int) int64 {
	// 注：排序只是为了找中位数，如果用快速选择算法，可以做到 O(n)
	slices.Sort(nums)

	// 返回所有 nums[i] 变成 pal[i] 的总代价
	cost := func(i int) (res int64) {
		target := pal[i]
		for _, x := range nums {
			res += int64(abs(x - target))
		}
		return
	}

	n := len(nums)
	i := sort.SearchInts(pal, nums[(n-1)/2]) // 二分找中位数右侧最近的回文数
	if pal[i] <= nums[n/2] { // 回文数在中位数范围内
		return cost(i) // 直接变成 pal[i]
	}
	return min(cost(i-1), cost(i)) // 枚举离中位数最近的两个回文数 pal[i-1] 和 pal[i]
}

func abs(x int) int { if x < 0 { return -x }; return x }

cpp 解法, 执行用时: 80 ms, 内存消耗: 51.1 MB, 提交时间: 2023-12-17 23:36:49

vector<int> pal;

auto init = [] {
    // 严格按顺序从小到大生成所有回文数（不用字符串转换）
    for (int base = 1; base <= 10000; base *= 10) {
        // 生成奇数长度回文数
        for (int i = base; i < base * 10; i++) {
            int x = i;
            for (int t = i / 10; t; t /= 10) {
                x = x * 10 + t % 10;
            }
            pal.push_back(x);
        }
        // 生成偶数长度回文数
        if (base <= 1000) {
            for (int i = base; i < base * 10; i++) {
                int x = i;
                for (int t = i; t; t /= 10) {
                    x = x * 10 + t % 10;
                }
                pal.push_back(x);
            }
        }
    }
    pal.push_back(1'000'000'001); // 哨兵，防止下面代码中的 i 下标越界
    return 0;
}();

class Solution {
public:
    long long minimumCost(vector<int> &nums) {
        // 注：排序只是为了找中位数，如果用快速选择算法，可以做到 O(n)
        sort(nums.begin(), nums.end());

        // 返回 nums 中的所有数变成 pal[i] 的总代价
        auto cost = [&](int i) -> long long {
            int target = pal[i];
            long long sum = 0;
            for (int x: nums) {
                sum += abs(x - target);
            }
            return sum;
        };

        int n = nums.size();
        // 二分找中位数右侧最近的回文数
        int i = lower_bound(pal.begin(), pal.end(), nums[(n - 1) / 2]) - pal.begin();
        if (pal[i] <= nums[n / 2]) { // 回文数在中位数范围内
            return cost(i); // 直接变成 pal[i]
        }
        return min(cost(i - 1), cost(i)); // 枚举离中位数最近的两个回文数 pal[i-1] 和 pal[i]
    }
};

上一题

下一题

详情