CS-Wiki CS-Wiki
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
  • 刷题模板汇总
  • 一些刷题小技巧
  • 整数 and 位运算

  • 数组

  • 链表

  • 哈希表

  • 字符串

  • 栈

  • 队列

  • 二叉树

  • 前缀树

  • 二分查找

  • 双指针法

  • 区间求和问题

  • 排序

  • 回溯算法

  • 贪心算法

    • 贪心算法理论基础
    • 找零
    • 柠檬水找零
    • 分发饼干
    • K 次取反后最大化的数组和
    • 加油站
    • 分发糖果
    • 根据身高重建队列
    • 划分字母区间
    • 单调递增的数字
    • 监控二叉树
    • 使数组变成交替数组的最少操作数
      • 📃 题目描述
      • 🔔 解题思路
      • 💥 复杂度分析
    • 剑指 Offer 14- II - 剪绳子 II
    • 区间调度问题

  • 动态规划

  • 图

  • 数学

  • 自动机

  • 海量数据和空间限制

  • 05-数据结构与算法
  • 贪心算法
小牛肉
2022-08-27
目录

使数组变成交替数组的最少操作数

# 📃 题目描述

题目链接: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
监控二叉树
剑指 Offer 14- II - 剪绳子 II

← 监控二叉树 剑指 Offer 14- II - 剪绳子 II→

最近更新
01
02
线上环境 CPU 使用率飙升如何快速排查?
03-05
03
面试官再跟你说中国没有根服务器,雪人计划让他了解下
02-23
更多文章>
Theme by Vdoing | Copyright © 2019-2023 飞天小牛肉 | 皖ICP备2022008966号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式