使数组变成交替数组的最少操作数
难度:
标签:
题目描述
代码结果
运行时间: 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,这种情况下是否有其他可能的操作?
▷