给你一个长度为 n 、下标从 0 开始的整数数组 nums ，表示收集不同巧克力的成本。每个巧克力都对应一个不同的类型，最初，位于下标 i 的巧克力就对应第 i 个类型。 在一步操作中，你可以用成本 x 执行下述行为： 同时对于所有下标 0 <= i < n - 1 进行以下操作， 将下标 i 处的巧克力的类型更改为下标 (i + 1) 处的巧克力对应的类型。如果 i == n - 1 ，则该巧克力的类型将会变更为下标 0 处巧克力对应的类型。 假设你可以执行任意次操作，请返回收集所有类型巧克力所需的最小成本。

这是一个比较经典的贪心问题，可以用数学的方法求解。我们可以先计算出数组 nums 的平均值，然后遍历数组，将每个数与平均值的差累加起来，得到的结果就是最小成本。

证明如下：

设数组 nums 的平均值为 avg，数组长度为 n，数组中第 i 个元素的值为 nums[i]。

假设最优解中第 i 个元素的值为 opt[i]。

则有：

sum(nums[i] - avg) = sum(opt[i] - avg) + k * (opt[0] - avg)

其中，k 为操作次数。

因为所有的元素最终都会变成 opt[0]，所以最终的操作次数 k 等于 n。

将上面的式子化简，得到：

sum(nums[i] - opt[i]) = n * (opt[0] - avg)

因为 n 固定，所以要使得 sum(nums[i] - opt[i]) 最小，只需要使得 opt[0] 和 avg 的差最小即可。

因此，最优解中所有元素的值相等，等于数组 nums 的平均值。

时间复杂度为 O(n)，空间复杂度为 O(1)。

相关问题

给你一个下标从 0 开始的整数数组 nums ，数组长度为 n 。 你可以执行无限次下述运算： 选择一个之前未选过的下标 i ，并选择一个 严格小于 nums[i] 的质数 p ，从 nums[i] 中减去 p 。 如果你能通过上述运算使得 nums 成为严格递增数组，则返回 true ；否则返回 false 。 严格递增数组 中的每个元素都严格大于其前面的元素。请用Python代码表示出来

class Solution:
    def isStrictlyIncreasing(self, nums: List[int]) -> bool:
        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
        for i in range(1, len(nums)):
            if nums[i] <= nums[i-1]:
                diff = nums[i-1] - nums[i] + 1
                found_prime = False
                for p in primes:
                    if p < diff:
                        found_prime = True
                        break
                if not found_prime:
                    return False
        return True

给你一个下标从 0 开始的整数数组 nums 。在一步操作中，你可以执行以下步骤： 从 nums 选出 两个 相等的 整数 从 nums 中移除这两个整数，形成一个 数对 请你在 nums 上多次执行此操作直到无法继续执行。 返回一个下标从 0 开始、长度为 2 的整数数组 answer 作为答案，其中 answer[0] 是形成的数对数目，answer[1] 是对 nums 尽可能执行上述操作后剩下的整数数目。 java实现

以下是 Java 实现代码：

public int[] findNums(int[] nums) {
    int[] answer = new int[2];
    Map<Integer, Integer> map = new HashMap<>();

    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }

    int count = 0;
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        int val = entry.getValue();
        count += val / 2;
        map.put(entry.getKey(), val % 2);
    }

    answer[0] = count;
    answer[1] = nums.length - count * 2;

    return answer;
}

这个实现使用 HashMap 来记录每个数字出现的次数，然后遍历 HashMap 计算出数对的数量和剩余数字的数量。具体来说，我们可以遍历 HashMap 中的每个键值对，计算当前键值对中可以组成的数对数量，然后更新键值对中的值，使其表示剩余的数字数量。最后，我们将答案放入一个长度为 2 的数组中并返回。