📃 题目描述

题目链接：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};
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：