leetcode
leetcode 2101 ~ 2150
使数组相似的最少操作次数

使数组相似的最少操作次数

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
为什么在解决此问题时要将数组分成奇数和偶数两部分?这种分法对解题有什么具体帮助?
在这个问题中,每次操作可以使一个元素增加2,另一个元素减少2。这样的操作保持了每个元素奇偶性的不变性,即奇数加2或减2后仍为奇数,偶数同理。因此,为了确保最终的`nums`数组与`target`数组在元素频率上相等,我们必须单独考虑奇数和偶数,确保奇数部分的元素可以通过有限操作转换为目标奇数部分,偶数部分同理。这种分法可以减少问题的复杂性,允许我们独立处理两部分,简化操作过程和计算。
🦆
在计算两数组元素差值时,只考虑了`nums`中的元素大于`target`中的元素的情况,若`nums`中的元素小于`target`中的元素,应该如何处理?
题解中只计算了`nums`元素大于`target`元素的情况,这是因为如果`nums`中的元素小于`target`中的元素,通过排序和索引匹配,这种情况会自动平衡。具体来说,如果一个较小的`nums`元素与较大的`target`元素对应,那么在其他位置一定存在一个较大的`nums`元素与较小的`target`元素对应,以保持两个数组的总和相同。因此,对于每一对`x > y`的情况,我们计算差值并除以2来确定操作数,而对于`x < y`的情况,它将被`x > y`的对应情况所平衡。
🦆
题解中提到每次操作可以使得一个元素加2,另一个元素减2,为什么在计算操作次数时使用`(x-y) >> 1`来确定需要的操作次数?这样的计算是否完全准确?
使用`(x-y) >> 1`来计算操作次数是因为每次操作改变的总量为2(一个元素加2,另一个减2),因此当我们发现`nums`中的元素`x`比`target`中的元素`y`大时,差值`x-y`表示为了匹配这两个元素,我们需要减小`x`或增加`y`的总量。由于每次操作改变的总量为2,所以将差值除以2(在计算中使用位移操作`>> 1`实现除以2)得到实际的操作次数。这样的计算考虑到了每对不匹配元素之间的差值,并且是准确的,前提是保持两个数组的元素总和相等,这在题设中是由排序和逐一比较保证的。

相关问题