leetcode
leetcode 1901 ~ 1950
使数组变成交替数组的最少操作数

使数组变成交替数组的最少操作数

难度:

标签:

题目描述

代码结果

运行时间: 103 ms, 内存: 29.7 MB


/*
 * Using Java Stream API, the problem is solved similarly to the Java solution.
 * We compute the frequency of numbers at even and odd indices using streams.
 * Then we determine the most frequent elements and calculate the minimum operations.
 */
import java.util.*;
import java.util.stream.*;

public class SolutionStream {
    public int minimumOperations(int[] nums) {
        int n = nums.length;

        Map<Integer, Long> evenFreq = IntStream.range(0, n).filter(i -> i % 2 == 0)
                .mapToObj(i -> nums[i])
                .collect(Collectors.groupingBy(e -> e, Collectors.counting()));

        Map<Integer, Long> oddFreq = IntStream.range(0, n).filter(i -> i % 2 != 0)
                .mapToObj(i -> nums[i])
                .collect(Collectors.groupingBy(e -> e, Collectors.counting()));

        int[] evenTop = getTopTwo(evenFreq);
        int[] oddTop = getTopTwo(oddFreq);

        if (evenTop[0] != oddTop[0]) {
            return (n / 2 - evenTop[1]) + (n - n / 2 - oddTop[1]);
        } else {
            return Math.min((n / 2 - evenTop[1]) + (n - n / 2 - oddTop[2]),
                            (n / 2 - evenTop[2]) + (n - n / 2 - oddTop[1]));
        }
    }

    private int[] getTopTwo(Map<Integer, Long> freq) {
        int first = 0, second = 0;
        long firstCount = 0, secondCount = 0;
        for (Map.Entry<Integer, Long> entry : freq.entrySet()) {
            int num = entry.getKey();
            long count = entry.getValue();
            if (count > firstCount) {
                second = first;
                secondCount = firstCount;
                first = num;
                firstCount = count;
            } else if (count > secondCount) {
                second = num;
                secondCount = count;
            }
        }
        return new int[]{first, (int) firstCount, second, (int) secondCount};
    }
}

解释

方法:

此题解的思路是将原数组分成两个子数组,一个包含所有偶数索引的元素,另一个包含所有奇数索引的元素。然后分别统计这两个子数组中元素的出现频率,并找出出现频率最高的两个元素(如果存在的话)。主要的考虑是:1. 最频繁出现在偶数索引位置的元素和最频繁出现在奇数索引位置的元素不相同时,我们只需要将其他元素更改为这两个元素即可。2. 如果两者相同,则需要考虑第二频繁的元素,以确保交替模式的成立。这涉及到比较更改后的总成本,选择最小的操作数。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在处理偶数和奇数索引的子数组时,要选择出现频率最高的两个元素来进行操作?
在处理偶数和奇数索引的子数组时,选择出现频率最高的两个元素是为了最大限度减少需要进行的更改次数。目标是使数组在偶数位置和奇数位置上的元素交替出现。如果我们选择频率最高的元素作为目标元素,那么需要更改的元素数量会最少。如果最频繁的元素在偶数和奇数索引中相同,我们需要考虑第二频繁的元素来确保可以形成交替模式,这就是为什么需要考虑两个最频繁的元素。
🦆
在最频繁的元素相同时,为什么选择最小操作数是通过比较 n - even[0][1] - odd[1][1] 和 n - even[1][1] - odd[0][1] 而得出?
当偶数索引和奇数索引的最频繁元素相同时,直接使用这两个元素会导致所有偶数位置和所有奇数位置上的元素都一样,无法形成交替模式。因此,我们必须选择一个不同的元素作为其中一个位置的目标元素。通过计算更改偶数索引最频繁元素和奇数索引第二频繁元素(或者相反)所需的操作数,可以找到需要最小更改次数的方案。这两种方案的最小值即为所需的最少操作数,确保数组能成功转换成交替数组。
🦆
如果偶数和奇数索引的数组中存在多种元素出现频率相同且最高,算法是如何处理这种情况?
如果偶数和奇数索引的数组中存在多种元素出现频率相同且最高,算法将从这些元素中选择任意一个作为最频繁的元素。如果这些元素之间可以形成交替模式,即它们在偶数位置和奇数位置互不相同,则直接选择其中的任意组合。如果这些最高频率的元素相同,则会进一步考虑次频繁的元素,以确保可以形成有效的交替模式。因此,算法可以灵活应对多个最高频率元素的情况,选择使更改操作最小化的组合。
🦆
为什么在长度为1的数组中直接返回0,这种情况下是否有其他可能的操作?
在长度为1的数组中直接返回0是因为单个元素的数组本身已经符合交替数组的定义,因为不存在相邻元素。所以,无需进行任何操作就已经是交替数组。在这种情况下,不存在其他的操作需求或可能性,因为任何更改都是不必要的。

相关问题