使数组相似的最少操作次数
难度:
标签:
题目描述
代码结果
运行时间: 148 ms, 内存: 31.9 MB
/*
* 思路:
* 1. 使用流计算 nums 和 target 中每个元素的频率。
* 2. 找出所有在 nums 中出现频率比 target 多的数和少的数。
* 3. 使用贪心算法,将多的数通过操作变成少的数,记录操作次数。
*/
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class MinOperationsStream {
public int minOperations(int[] nums, int[] target) {
Map<Integer, Long> numsCount = IntStream.of(nums).boxed()
.collect(Collectors.groupingBy(n -> n, Collectors.counting()));
Map<Integer, Long> targetCount = IntStream.of(target).boxed()
.collect(Collectors.groupingBy(n -> n, Collectors.counting()));
long operations = numsCount.entrySet().stream()
.filter(entry -> entry.getValue() > targetCount.getOrDefault(entry.getKey(), 0L))
.mapToLong(entry -> entry.getValue() - targetCount.getOrDefault(entry.getKey(), 0L))
.sum();
return (int) (operations / 2);
}
}
解释
方法:
该题解的思路基于将两个数组分别变为相似的过程。首先,将nums和target数组分别按奇偶性分开,形成四个子数组:nums的奇数部分、nums的偶数部分、target的奇数部分和target的偶数部分。针对这四个子数组,我们只需要分别使nums的奇数部分与target的奇数部分相似,以及nums的偶数部分与target的偶数部分相似即可。为了实现这一点,对于每个子数组,我们首先对其进行排序,然后逐对比较元素。如果nums中的元素大于target中的对应元素,我们计算差值的一半(因为每次操作改变的总和为2)并累加至操作次数。最后将奇数部分和偶数部分所需的操作次数求和,得到总的最少操作次数。
时间复杂度:
O(n log n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在解决此问题时要将数组分成奇数和偶数两部分?这种分法对解题有什么具体帮助?
▷🦆
在计算两数组元素差值时,只考虑了`nums`中的元素大于`target`中的元素的情况,若`nums`中的元素小于`target`中的元素,应该如何处理?
▷🦆
题解中提到每次操作可以使得一个元素加2,另一个元素减2,为什么在计算操作次数时使用`(x-y) >> 1`来确定需要的操作次数?这样的计算是否完全准确?
▷