当前位置:网站首页>LeetCode 6005. The minimum operand to make an array an alternating array
LeetCode 6005. The minimum operand to make an array an alternating array
2022-07-06 00:09:00 【Daylight629】
6005. The minimum number of operands to make an array an alternating array
I'll give you a subscript from 0 Starting array nums
, The array consists of n
It's made up of four positive integers .
If the following conditions are met , The array nums
It's a Alternating array :
nums[i - 2] == nums[i]
, among2 <= i <= n - 1
.nums[i - 1] != nums[i]
, among1 <= i <= n - 1
.
In one step operation in , You can choose the subscript i
And will nums[i]
change by any Positive integer .
Returns the that makes the array an alternating array The minimum number of operands .
Example 1:
Input :nums = [3,1,3,2,4,3]
Output :3
explain :
One way to turn an array into an alternating array is to convert the array to [3,1,3,1,3,1] .
under these circumstances , The operands are 3 .
Can prove that , Operands are less than 3 Under the circumstances , Cannot make an array into an alternating array .
Example 2:
Input :nums = [1,2,2,2,2]
Output :2
explain :
One way to turn an array into an alternating array is to convert the array to [1,2,1,2,1].
under these circumstances , The operands are 2 .
Be careful , Array cannot be converted to [2,2,2,2,2] . Because in this case ,nums[0] == nums[1], The condition of alternating array is not satisfied .
Tips :
1 <= nums.length <= 105
1 <= nums[i] <= 105
Two 、 Method 1
Count the most frequent occurrences of , Then find the one that appears the most and the second most , If it's not equal, subtract these , If equal, subtract the maximum sum
class Solution {
public int minimumOperations(int[] nums) {
Map<Integer, Integer> map1 = new HashMap<>();
Map<Integer, Integer> map2 = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if ((i & 1) == 1) {
map1.put(nums[i], map1.getOrDefault(nums[i], 0) + 1);
} else {
map2.put(nums[i], map2.getOrDefault(nums[i], 0) + 1);
}
}
int x1 = 0;
int x2 = 0;
int y1 = 0;
int y2 = 0;
int a = 0;
int b = 0;
int c = 0;
int d = 0;
for (Map.Entry<Integer,Integer> entry : map1.entrySet()) {
if (entry.getValue() > a) {
b = a;
a = entry.getValue();
x1 = entry.getKey();
}
else if (entry.getValue() > b) {
b = entry.getValue();
}
}
for (Map.Entry<Integer,Integer> entry : map2.entrySet()) {
if (entry.getValue() > c) {
d = c;
c = entry.getValue();
y1 = entry.getKey();
}
else if (entry.getValue() > d) {
d = entry.getValue();
}
}
if (x1 == y1) {
return nums.length - Math.max(a + d, b + c);
} else {
return nums.length - (a + c);
}
}
}
Complexity analysis
Time complexity :O(n).
Spatial complexity :O(n).
边栏推荐
- N1 # if you work on a metauniverse product [metauniverse · interdisciplinary] Season 2 S2
- 18.(arcgis api for js篇)arcgis api for js点采集(SketchViewModel)
- 20220703 week race: number of people who know the secret - dynamic rules (problem solution)
- Recognize the small experiment of extracting and displaying Mel spectrum (observe the difference between different y_axis and x_axis)
- 什么叫做信息安全?包含哪些内容?与网络安全有什么区别?
- 多普勒效應(多普勒頻移)
- XML configuration file (DTD detailed explanation)
- Global and Chinese markets of POM plastic gears 2022-2028: Research Report on technology, participants, trends, market size and share
- Huawei equipment is configured with OSPF and BFD linkage
- 单商户V4.4,初心未变,实力依旧!
猜你喜欢
妙才周刊 - 8
How to rotate the synchronized / refreshed icon (EL icon refresh)
The difference of time zone and the time library of go language
C reflection and type
Qt QPushButton详解
China Jinmao online electronic signature, accelerating the digitization of real estate business
Transport layer protocol ----- UDP protocol
Upgrade openssl-1.1.1p for openssl-1.0.2k
软件测试工程师必会的银行存款业务,你了解多少?
Open source CRM customer relationship system management system source code, free sharing
随机推荐
【GYM 102832H】【模板】Combination Lock(二分图博弈)
Global and Chinese markets of POM plastic gears 2022-2028: Research Report on technology, participants, trends, market size and share
How much do you know about the bank deposit business that software test engineers must know?
Doppler effect (Doppler shift)
教你在HbuilderX上使用模拟器运行uni-app,良心教学!!!
MySQL之函数
Effet Doppler (déplacement de fréquence Doppler)
云呐|固定资产管理系统主要操作流程有哪些
FFMPEG关键结构体——AVFormatContext
总结了 800多个 Kubectl 别名,再也不怕记不住命令了!
7.5 decorator
权限问题:source .bash_profile permission denied
如何解决ecology9.0执行导入流程流程产生的问题
Configuring OSPF load sharing for Huawei devices
Open source CRM customer relationship system management system source code, free sharing
用列表初始化你的vector&&initializer_list简介
转:未来,这样的组织才能扛住风险
N1 # if you work on a metauniverse product [metauniverse · interdisciplinary] Season 2 S2
QT QPushButton details
【QT】Qt使用QJson生成json文件并保存