class Solution {
public:
int minimumOperations(vector<int>& nums) {
}
};
2170. 使数组变成交替数组的最少操作数
给你一个下标从 0 开始的数组 nums ，该数组由 n 个正整数组成。
如果满足下述条件，则数组 nums 是一个 交替数组 ：
nums[i - 2] == nums[i] ，其中 2 <= i <= n - 1 。nums[i - 1] != nums[i] ，其中 1 <= i <= n - 1 。在一步 操作 中，你可以选择下标 i 并将 nums[i] 更改 为 任一 正整数。
返回使数组变成交替数组的 最少操作数 。
示例 1：
输入：nums = [3,1,3,2,4,3] 输出：3 解释： 使数组变成交替数组的方法之一是将该数组转换为 [3,1,3,1,3,1] 。 在这种情况下，操作数为 3 。 可以证明，操作数少于 3 的情况下，无法使数组变成交替数组。
示例 2：
输入：nums = [1,2,2,2,2] 输出：2 解释： 使数组变成交替数组的方法之一是将该数组转换为 [1,2,1,2,1]. 在这种情况下，操作数为 2 。 注意，数组不能转换成 [2,2,2,2,2] 。因为在这种情况下，nums[0] == nums[1]，不满足交替数组的条件。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 105原站题解
java 解法, 执行用时: 11 ms, 内存消耗: 55.1 MB, 提交时间: 2023-07-12 09:48:30
class Solution {
public int minimumOperations(int[] nums) {
int n = nums.length;
int[] cnt1 = new int[100010];
int[] cnt2 = new int[100010];
int a = 0, b = 0, c = 0, d = 0;
for (int i = 0; i < n; i++) {
int x = nums[i];
if (i % 2 == 0) {
++cnt1[x];
if (cnt1[x] > cnt1[a]) {
b = a;
a = x;
} else if (x != a && cnt1[x] > cnt1[b]) b = x;
} else {
++cnt2[x];
if (cnt2[x] > cnt2[c]) {
d = c;
c = x;
} else if (x != c && cnt2[x] > cnt2[d]) d = x;
}
}
if (a != c) return n - cnt1[a] - cnt2[c];
return n - Math.max(cnt1[a] + cnt2[d], cnt1[b] + cnt2[c]);
}
}
python3 解法, 执行用时: 140 ms, 内存消耗: 29.8 MB, 提交时间: 2023-07-12 09:47:15
class Solution:
def minimumOperations(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return 0
# 奇偶统计 分别得到出现次数最多和次多的元素及其对应频次
cnt0 = Counter(nums[::2]).most_common(2) # 偶数组统计：下标0开始，间隔为2
cnt1 = Counter(nums[1::2]).most_common(2) # 奇数组统计：下标1开始，间隔为2
if cnt0[0][0] != cnt1[0][0]: # 两个数组中，出现次数最多的元素不同
return n-cnt0[0][1]-cnt1[0][1]
else: # 两个数组中，出现次数最多的元素相同
cost0 = n - cnt0[0][1] - (0 if len(cnt1)==1 else cnt1[1][1]) # 保留偶数组中出现次数最多的元素，并考虑保留奇数组中出现次数第二多（如存在）的元素
cost1 = n - cnt1[0][1] - (0 if len(cnt0)==1 else cnt0[1][1]) # 保留奇数组中出现次数最多的元素，并考虑保留偶数组中出现次数第二多（如存在）的元素
return min(cost0, cost1) # 两种情况取最小值
cpp 解法, 执行用时: 260 ms, 内存消耗: 137.1 MB, 提交时间: 2023-07-12 09:46:02
class Solution {
public:
int minimumOperations(vector<int>& nums) {
int n = nums.size();
// start = 0 表示偶数下标，start = 1 表示奇数下标
// 返回值为最大键，最大键对应的值，次大键，次大键对应的值
auto get = [&](int start) -> tuple<int, int, int, int> {
unordered_map<int, int> freq;
for (int i = start; i < n; i += 2) {
++freq[nums[i]];
}
int fstkey = 0, fstval = 0, sndkey = 0, sndval = 0;
for (const auto& [key, val]: freq) {
if (val > fstval) {
tie(sndkey, sndval) = tuple{fstkey, fstval};
tie(fstkey, fstval) = tuple{key, val};
}
else if (val > sndval) {
tie(sndkey, sndval) = tuple{key, val};
}
}
return {fstkey, fstval, sndkey, sndval};
};
auto [e1stkey, e1stval, e2ndkey, e2ndval] = get(0);
auto [o1stkey, o1stval, o2ndkey, o2ndval] = get(1);
if (e1stkey != o1stkey) {
return n - (e1stval + o1stval);
}
return n - max(e1stval + o2ndval, o1stval + e2ndval);
}
};
python3 解法, 执行用时: 128 ms, 内存消耗: 29.7 MB, 提交时间: 2023-07-12 09:45:37
# 选择奇偶下标出现次数最多的数
class Solution:
def minimumOperations(self, nums: List[int]) -> int:
n = len(nums)
# start = 0 表示偶数下标，start = 1 表示奇数下标
# 返回值: [最大键，最大键对应的值，次大键，次大键对应的值]
def get(start: int) -> Tuple[int, int, int, int]:
freq = Counter(nums[start::2])
best = freq.most_common(2)
if not best:
return 0, 0, 0, 0
if len(best) == 1:
return *best[0], 0, 0
return *best[0], *best[1]
e1stkey, e1stval, e2ndkey, e2ndval = get(0)
o1stkey, o1stval, o2ndkey, o2ndval = get(1)
if e1stkey != o1stkey:
return n - (e1stval + o1stval)
return n - max(e1stval + o2ndval, o1stval + e2ndval)
golang 解法, 执行用时: 228 ms, 内存消耗: 10.5 MB, 提交时间: 2023-07-12 09:43:29
type pair struct{ num, cnt int }
// 计算出现次数最多的两个元素及其出现次数
func getMaxCnt2(cnt map[int]int) []pair {
a := make([]pair, 0, max(len(cnt), 2))
for num, c := range cnt {
a = append(a, pair{num, c})
}
sort.Slice(a, func(i, j int) bool { return a[i].cnt > a[j].cnt })
return a[:2] // 不足两个时，用 pair{0, 0} 填充
}
func minimumOperations(nums []int) int {
cnt := [2]map[int]int{{}, {}}
for i, num := range nums {
cnt[i&1][num]++
}
a0 := getMaxCnt2(cnt[0])
a1 := getMaxCnt2(cnt[1])
if a0[0].num != a1[0].num {
return len(nums) - a0[0].cnt - a1[0].cnt // 不相等时，保留出现次数最多的两个
}
return len(nums) - max(a0[0].cnt+a1[1].cnt, a0[1].cnt+a1[0].cnt) // 相等时，保留出现次数最多的和另一个出现次数次多的
}
func max(a, b int) int { if b > a { return b }; return a }