1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# @Title: 使数组变成交替数组的最少操作数 (Minimum Operations to Make the Array Alternating)
# @Author: 15816537946@163.com
# @Date: 2022-02-13 12:46:26
# @Runtime: 196 ms
# @Memory: 31.2 MB
class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        
        n = len(nums)
        if n == 1:
            return 0
        
        cnt0 = Counter(nums[::2])   # 从0开始，间隔为2
        cnt1 = Counter(nums[1::2])  # 从1开始，间隔为2
        
        cnt0 = sorted(cnt0.items(), key=lambda x: -x[1])    # 按照出现次数倒序排列
        cnt1 = sorted(cnt1.items(), key=lambda x: -x[1])
        
        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)    # 两种情况取最小值