665. 非递减数列 - 力扣（LeetCode）
给你一个长度为 n 的整数数组 nums ，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。
我们是这样定义一个非递减数列的： 对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。
解题思路
遍历数组，计算递减对，显然当递减对＞1时，不满足条件，当递减对=0时，满足条件。容易忽视的时当递减对=1时的情况：
代码实现
class Solution {
public:
bool checkPossibility(vector<int>& nums) {
int count = 0;
int temp = -1;
for(int i = 0; i < nums.size()-1; i++){
if(nums[i]>nums[i+1]){
count++;
temp = i;
}
}
if(count>1){
return false;
}
if(count==0){
return true;
}
if(temp==0||nums[temp-1]<=nums[temp+1]){
return true;
}
if(temp==nums.size()-2||nums[temp]<=nums[temp+2]){
return true;
}
return false;
}
};2032. 至少在两个数组中出现的值 - 力扣（LeetCode）
给你三个整数数组 nums1、nums2 和 nums3 ，请你构造并返回一个 元素各不相同的 数组，且由 至少 在 两个 数组中出现的所有值组成。数组中的元素可以按 任意 顺序排列。
解题思路
1° 统计每个元素的出现次数：定义哈希表，遍历每个数组，然后对出现的元素进行异或处理。
2° 筛选出出现次数≥2的元素：然后根据得到的异或结果再进行与运算。
3° 具体操作解析如下：
如果元素在2个或3个数组中出现过，那么它的与运算（v&(v-1)）的二进制结果中仍有1存在（即结果不为0），将符合条件的该元素加进结果数组中即可。
代码实现
class Solution {
public:
vector<int> twoOutOfThree(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3) {
unordered_map<int, int> mp;
for (auto& i : nums1) {
mp[i] = 1;
}
for (auto& i : nums2) {
mp[i] |= 2;
}
for (auto& i : nums3) {
mp[i] |= 4;
}
vector<int> res;
for (auto& [k, v] : mp) {
if (v & (v - 1)) {
res.push_back(k);
}
}
return res;
}
};2170. 使数组变成交替数组的最少操作数 - 力扣（LeetCode）
给你一个下标从 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° 遍历数组，更新哈希表的值（也就是统计奇偶数位各数的出现次数）
2° 定义若干变量记录奇偶位出现次数最多和第二多的键和键值。通过遍历奇偶哈希表获得所需要的值。
3° 添加判断条件，即②中的步骤。最后返回即可。
代码实现
class Solution {
public:
int minimumOperations(vector<int>& nums) {
unordered_map<int, int> odd;
unordered_map<int, int> even;
for(int i = 0; i < nums.size(); i++){
if(i % 2 == 0){
even[nums[i]]++;
} else {
odd[nums[i]]++;
}
}
int oddMax = 0;
int oddSecondMax = 0;
int evenMax = 0;
int evenSecondMax = 0;
int oddMaxKey = 0;
int evenMaxKey = 0;
for(auto it = odd.begin(); it != odd.end(); it++){
if(it->second >= oddMax){
oddSecondMax = oddMax;
oddMax = it->second;
oddMaxKey = it->first;
} else if(it->second > oddSecondMax){
oddSecondMax = it->second;
}
}
for(auto it = even.begin(); it != even.end(); it++){
if(it->second >= evenMax){
evenSecondMax = evenMax;
evenMax = it->second;
evenMaxKey = it->first;
} else if(it->second > evenSecondMax){
evenSecondMax = it->second;
}
}
if(oddMaxKey!=evenMaxKey){
return nums.size()-oddMax-evenMax;
}
return nums.size()- max(oddMax + evenSecondMax, evenMax + oddSecondMax);
}
};