使数组变成交替数组的最少操作数
# 📃 题目描述
题目链接:2170. 使数组变成交替数组的最少操作数 (opens new window)
# 🔔 解题思路
京东笔试原题
class Solution {
public int minimumOperations(int[] nums) {
if (nums == null || nums.length <= 1) {
return 0;
}
// key:num, value: num 出现的次数
Map<Integer, Integer> oddMap = new HashMap<>();
Map<Integer, Integer> evenMap = new HashMap<>();
for (int i = 0; i < nums.length; i ++) {
if ((i + 1) % 2 != 0) {
oddMap.put(nums[i], oddMap.getOrDefault(nums[i], 0) + 1);
}
else {
evenMap.put(nums[i], evenMap.getOrDefault(nums[i], 0) + 1);
}
}
int[] odd = get(oddMap);
int oddMaxCount = oddMap.get(odd[0]);
// 出现次数第二多的数很可能不存在,即所有的奇数都相等
int oddSecondCount = odd[1] == -1 ? 0 : oddMap.get(odd[1]);
int[] even = get(evenMap);
int evenMaxCount = evenMap.get(even[0]);
// 出现次数第二多的数很可能不存在,即所有的偶数都相等
int evenSecondCount = even[1] == -1 ? 0 : evenMap.get(even[1]);
if (odd[0] != even[0]) {
return nums.length - oddMaxCount - evenMaxCount;
}
return nums.length - Math.max(oddMaxCount + evenSecondCount, evenMaxCount + oddSecondCount);
}
// 返回 map 中出现次数最多(int[0])和第二最多的数(int[1])
private int[] get(Map<Integer, Integer> map) {
// 出现次数最多的数
int a = -1;
int maxCount = 0;
// 出现次数第二多的数
int b = -1;
int secondCount = 0;
for (int key : map.keySet()) {
if(map.get(key) > maxCount) {
a = key;
maxCount = map.get(key);
}
}
for (int key : map.keySet()) {
if (map.get(key) > secondCount && key != a) {
b = key;
secondCount = map.get(key);
}
}
return new int[]{a, b};
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10