首页 > 其他分享 >2170.使数组变成交替数组的最少操作数

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

时间:2023-06-13 16:57:52浏览次数:43  
标签:操作数 num1 num2 nums max second 2170 数组

问题描述

2170. 使数组变成交替数组的最少操作数 (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⁵
  • 1 <= nums[i] <= 10⁵

解题思路

贪心,分别记录nums的奇数索引的元素中出现最多的两个元素及其出现次数,记为max_2, max_num2, second_2, second_num2,以及nums的偶数索引的元素中出现最多的两个元素及其出现次数,记为max_1, max_num1, second_1, second_num1,如果max_1 != max_2,结果resnums.size() - max_num1 - max_num2,否则res = std::min(nums.size() - max_num1 - second_num2, nums.size() - second_num1 - max_num2)

代码

class Solution {
  public:
    // map,内部元素为pair<int, int> 数字以及数字出现个数
    int minimumOperations(vector<int> &nums) {
        auto cmp = [&](pair<int, int> &p1, pair<int, int> &p2) {
            return p1.second < p2.second;
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq1(cmp);
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq2(cmp);
        unordered_map<int, int> mp1, mp2;
        for (int i = 0; i < nums.size(); i += 2) {
            mp1[nums[i]]++;
            if (i + 1 < nums.size()) {
                mp2[nums[i + 1]]++;
            }
        }
        int max_1 = 0, second_1 = 0;
        int max_num1 = 0, second_num1 = 0;
        int max_2 = 0, second_2 = 0;
        int max_num2 = 0, second_num2 = 0;
        for (auto &p1 : mp1) {
            if (p1.second >= max_1) {
                second_1 = max_1;
                second_num1 = max_num1;
                max_1 = p1.second;
                max_num1 = p1.first;
            } else if (p1.second >= second_1) {
                second_1 = p1.second;
                second_num1 = p1.first;
            }
        }
        for (auto &p2 : mp2) {
            if (p2.second >= max_2) {
                second_2 = max_2;
                second_num2 = max_num2;
                max_2 = p2.second;
                max_num2 = p2.first;
            } else if (p2.second >= second_2) {
                second_2 = p2.second;
                second_num2 = p2.first;
            }
        }
        if (max_num1 != max_num2) {
            return nums.size() - max_1 - max_2;
        }
        return std::min(nums.size() - max_1 - second_2, nums.size() - max_2 - second_1);
    }
};

标签:操作数,num1,num2,nums,max,second,2170,数组
From: https://www.cnblogs.com/zwyyy456/p/17478101.html

相关文章

  • 442.数组中重复的数据 (Medium)
    问题描述442.数组中重复的数据(Medium)给你一个长度为n的整数数组nums,其中nums的所有整数都在范围[1,n]内,且每个整数出现一次或两次。请你找出所有出现两次的整数,并以数组形式返回。你必须设计并实现一个时间复杂度为O(n)且仅使用常量额外空间的算法解决此......
  • 795.区间子数组个数 (Medium)
    问题描述795.区间子数组个数(Medium)给你一个整数数组nums和两个整数:left及right。找出nums中连续、非空且其中最大元素在范围[left,right]内的子数组,并返回满足条件的子数组的个数。生成的测试用例保证结果符合32-bit整数范围。示例1:输入:nums=[2,1,4,3],......
  • 2023.6.13 数组中不等三元组的数目
    直接的思路是三重循环\(O(n^3)\)解决,由于数据范围是\(n\leq100\),所以\(n^3\leq10^6\)可以过。如果想稍微优化一下的话,可以考虑下面两种思路,都是类似的:排序,排完序后相同的元素会聚集到一起,假设他们聚集在了区间\([i,j]\)内。那\([0,i-1]\)这一部分区间和\([j+1,n]\)......
  • C/C++学习(10)关于数组、内联函数、虚函数的错题集锦
    1、顺序存储方式不仅用于存储线性结构,还可以用于存放非线性结构,如完全二叉树是属于非线性结构,但其最佳存储方式是顺序存储方式。 2、数组名有两重属性:1)数据结构的一个对象(数据结构为当前数组),在java中数组就是一个对象。2)某些情况下自动退化成指向第一个元素的常量指针。 3、有两......
  • 多维数组中指向的值
    #include<iostream>usingnamespacestd; intmain(){inta[2][2][3]={{{1,2,3},{4,5,6}},{{7,8,9},{10,11,12}}};int*ptr=(int*)(&a+1);printf("%d%d",*(int*)(a+1),*(ptr-1));return0;}输出结果为712*(int*)(a+1):指向数组a[......
  • 力扣---2475. 数组中不等三元组的数目
    给你一个下标从0开始的正整数数组nums。请你找出并统计满足下述条件的三元组(i,j,k)的数目:0<=i<j<k<nums.lengthnums[i]、nums[j]和nums[k]两两不同。换句话说:nums[i]!=nums[j]、nums[i]!=nums[k]且nums[j]!=nums[k]。返回满足上述条件三元组的数目......
  • 【易错点】数组名和数组取地址的区别
     inta[3]={1,2,3}; a: 数组名,数组中第一个元素的地址,相当于&a[0] &a:整个数组的地址,在数值上等于a a+1:数组中第二个元素的地址,相当于&a[1] &a+1:整个数组结束以后后面一个位置的地址 即:a=&a, 但 a+1≠&a+1 a[0]a[1]a[2]     ......
  • 代码随想录算法训练营第五天| 242.有效的字母异位词 , 349. 两个数组的交集 , 202. 快
    242.有效的字母异位词 繁冗版:1,思路:先建立两个map,对应两个字符串对应的字符,同时对他们进行计数,如果这两个数字相等,那么就是相等2,代码1boolisAnagram_complicate(strings,stringt)2{3unordered_map<char,int>existedCharBys;45for(autoch......
  • shell数组的差集
    https://stackoverflow.com/questions/29396154/jq-setdiff-of-two-arrays1.echo-n'{"all":["A","B","C","ABC"],"some":["B","C"]}'|jq'.as$d|.all|del(.[i......
  • 调整数组顺序使奇数位于偶数前面
    输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的前半部分,所有偶数在数组的后半部分。示例:输入:nums= [1,2,3,4]输出:[1,3,2,4]注:[3,1,2,4]也是正确的答案之一。来源:力扣(LeetCode)链接:https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-s......