Medium

题目描述

给你一个下标从 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 <= 10^5
  • 1 <= nums[i] <= 10^5

解题思路

解题思路

题目要求将数组变为交替数组，即奇数位置的元素都相同，偶数位置的元素都相同，且相邻元素不同。

贪心策略分析：

  1. 将数组按照索引奇偶性分为两组：奇数位置和偶数位置
  2. 统计每组中每个数字出现的频次
  3. 为了最小化操作次数，我们应该保留尽可能多的原有元素
  4. 最优策略是选择奇数位置出现最频繁的数字作为奇数位置的目标值，选择偶数位置出现最频繁的数字作为偶数位置的目标值

需要考虑的特殊情况：

  • 如果奇数位置和偶数位置的最高频数字相同，则需要选择次高频的数字之一
  • 如果某个位置只有一种数字，需要特殊处理

算法步骤：

  1. 分别统计奇数和偶数位置各数字的出现频次
  2. 找出每组的最高频和次高频数字
  3. 比较四种可能的组合，选择保留元素最多的方案
  4. 操作次数 = 总长度 - 保留的元素个数

代码实现

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return 0;
        
        // 统计奇数和偶数位置的元素频次
        unordered_map<int, int> oddCount, evenCount;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                evenCount[nums[i]]++;
            } else {
                oddCount[nums[i]]++;
            }
        }
        
        // 找出奇数位置的前两个高频元素
        vector<pair<int, int>> oddFreq;
        for (auto& p : oddCount) {
            oddFreq.push_back({p.second, p.first});
        }
        sort(oddFreq.rbegin(), oddFreq.rend());
        
        // 找出偶数位置的前两个高频元素
        vector<pair<int, int>> evenFreq;
        for (auto& p : evenCount) {
            evenFreq.push_back({p.second, p.first});
        }
        sort(evenFreq.rbegin(), evenFreq.rend());
        
        int maxKeep = 0;
        
        // 尝试所有可能的组合
        for (int i = 0; i < min(2, (int)oddFreq.size()); i++) {
            for (int j = 0; j < min(2, (int)evenFreq.size()); j++) {
                if (oddFreq[i].second != evenFreq[j].second) {
                    maxKeep = max(maxKeep, oddFreq[i].first + evenFreq[j].first);
                }
            }
        }
        
        return n - maxKeep;
    }
};

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return 0
        
        # 统计奇数和偶数位置的元素频次
        odd_count = {}
        even_count = {}
        
        for i in range(n):
            if i % 2 == 0:
                even_count[nums[i]] = even_count.get(nums[i], 0) + 1
            else:
                odd_count[nums[i]] = odd_count.get(nums[i], 0) + 1
        
        # 找出奇数位置的前两个高频元素
        odd_freq = sorted(odd_count.items(), key=lambda x: x[1], reverse=True)
        # 找出偶数位置的前两个高频元素
        even_freq = sorted(even_count.items(), key=lambda x: x[1], reverse=True)
        
        max_keep = 0
        
        # 尝试所有可能的组合
        for i in range(min(2, len(odd_freq))):
            for j in range(min(2, len(even_freq))):
                if odd_freq[i][0] != even_freq[j][0]:
                    max_keep = max(max_keep, odd_freq[i][1] + even_freq[j][1])
        
        return n - max_keep

public class Solution {
    public int MinimumOperations(int[] nums) {
        int n = nums.Length;
        if (n == 1) return 0;
        
        // 统计奇数和偶数位置的元素频次
        var oddCount = new Dictionary<int, int>();
        var evenCount = new Dictionary<int, int>();
        
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                evenCount[nums[i]] = evenCount.GetValueOrDefault(nums[i], 0) + 1;
            } else {
                oddCount[nums[i]] = oddCount.GetValueOrDefault(nums[i], 0) + 1;
            }
        }
        
        // 找出奇数位置的前两个高频元素
        var oddFreq = oddCount.OrderByDescending(p => p.Value).ToList();
        // 找出偶数位置的前两个高频元素
        var evenFreq = evenCount.OrderByDescending(p => p.Value).ToList();
        
        int maxKeep = 0;
        
        // 尝试所有可能的组合
        for (int i = 0; i < Math.Min(2, oddFreq.Count); i++) {
            for (int j = 0; j < Math.Min(2, evenFreq.Count); j++) {
                if (oddFreq[i].Key != evenFreq[j].Key) {
                    maxKeep = Math.Max(maxKeep, oddFreq[i].Value + evenFreq[j].Value);
                }
            }
        }
        
        return n - maxKeep;
    }
}

var minimumOperations = function(nums) {
    const n = nums.length;
    if (n === 1) return 0;
    
    const evenCount = new Map();
    const oddCount = new Map();
    
    for (let i = 0; i < n; i++) {
        if (i % 2 === 0) {
            evenCount.set(nums[i], (evenCount.get(nums[i]) || 0) + 1);
        } else {
            oddCount.set(nums[i], (oddCount.get(nums[i]) || 0) + 1);
        }
    }
    
    const evenPairs = Array.from(evenCount.entries()).sort((a, b) => b[1] - a[1]);
    const oddPairs = Array.from(oddCount.entries()).sort((a, b) => b[1] - a[1]);
    
    const evenLen = Math.ceil(n / 2);
    const oddLen = Math.floor(n / 2);
    
    let maxKeep = 0;
    
    for (let i = 0; i < Math.min(2, evenPairs.length); i++) {
        for (let j = 0; j < Math.min(2, oddPairs.length); j++) {
            if (evenPairs[i][0] !== oddPairs[j][0]) {
                maxKeep = Math.max(maxKeep, evenPairs[i][1] + oddPairs[j][1]);
            }
        }
    }
    
    if (maxKeep === 0) {
        if (evenPairs.length > 0) {
            maxKeep = Math.max(maxKeep, evenPairs[0][1]);
        }
        if (oddPairs.length > 0) {
            maxKeep = Math.max(maxKeep, oddPairs[0][1]);
        }
    }
    
    return n - maxKeep;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n + k log k)，其中 n 是数组长度，k 是不同元素个数。统计频次需要 O(n)，排序需要 O(k log k)
空间复杂度O(k)，需要额外的哈希表存储频次统计，k 是不同元素个数

相关题目