题目:
给你两个下标从 0 开始的数组 nums 和 cost ,分别包含 n 个 正 整数。
你可以执行下面操作 任意 次:
将 nums 中 任意 元素增加或者减小 1 。
对第 i 个元素执行一次操作的开销是 cost[i] 。
请你返回使 nums 中所有元素 相等 的 最少 总开销。
示例 1:
输入:nums = [1,3,5,2], cost = [2,3,1,14]
输出:8
解释:我们可以执行以下操作使所有元素变为 2 :
- 增加第 0 个元素 1 次,开销为 2 。
- 减小第 1 个元素 1 次,开销为 3 。
- 减小第 2 个元素 3 次,开销为 1 + 1 + 1 = 3 。
总开销为 2 + 3 + 3 = 8 。
这是最小开销。
示例 2:
输入:nums = [2,2,2,2,2], cost = [4,2,8,1,3]
输出:0
解释:数组中所有元素已经全部相等,不需要执行额外的操作。
提示:
n == nums.length == cost.length
1 <= n <= 10^5
1 <= nums[i], cost[i] <= 10^6
测试用例确保输出不超过 2^53-1。
java代码:
public class Solution {
public long minCost(int[] nums, int[] cost) {
int N = nums.length;
HashMap<Integer, Integer> map = new HashMap<>();
// 去重,相同的数字可以合并cost
for (int i = 0; i < N; i++) {
map.put(nums[i], map.getOrDefault(nums[i], 0) + cost[i]);
}
if (map.size() == 1) return 0;
long ans = Long.MAX_VALUE;
List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.size());
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
list.add(entry);
}
Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
return Integer.compare(o1.getKey(), o2.getKey());
}
});
long tmp = 0;
// 计算前缀和
long[] costSums = new long[list.size() + 1];
for (int j = 1; j <= list.size(); j++) {
costSums[j] = costSums[j - 1] + list.get(j - 1).getValue();
}
for (int i = 0; i < list.size(); i++) {
tmp += (long) (list.get(list.size() - 1).getKey() - list.get(i).getKey()) * list.get(i).getValue();
}
ans = Math.min(ans, tmp);
for (int i = list.size() - 2; i >= 0; i--) {
long right = (list.get(i + 1).getKey() - list.get(i).getKey()) * (costSums[list.size()] - costSums[i + 1]);
long left = (list.get(i + 1).getKey() - list.get(i).getKey()) * costSums[i + 1];
tmp = tmp - left + right;
if (ans > tmp) {
ans = tmp;
}
}
return ans;
}
}
网友评论