Greedy
Array
Hash Table
Counting
Description
You are given a 0-indexed array nums
consisting of n
positive integers.
The array nums
is called alternating if:
nums[i - 2] == nums[i]
, where 2 <= i <= n - 1
.
nums[i - 1] != nums[i]
, where 1 <= i <= n - 1
.
In one operation , you can choose an index i
and change nums[i]
into any positive integer.
Return the minimum number of operations required to make the array alternating .
Example 1:
Input: nums = [3,1,3,2,4,3]
Output: 3
Explanation:
One way to make the array alternating is by converting it to [3,1,3,1 ,3 ,1 ].
The number of operations required in this case is 3.
It can be proven that it is not possible to make the array alternating in less than 3 operations.
Example 2:
Input: nums = [1,2,2,2,2]
Output: 2
Explanation:
One way to make the array alternating is by converting it to [1,2,1 ,2,1 ].
The number of operations required in this case is 2.
Note that the array cannot be converted to [2 ,2,2,2,2] because in this case nums[0] == nums[1] which violates the conditions of an alternating array.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 105
Solutions
Solution 1
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12 class Solution :
def minimumOperations ( self , nums : List [ int ]) -> int :
def get ( i ):
c = Counter ( nums [ i :: 2 ]) . most_common ( 2 )
if not c :
return [( 0 , 0 ), ( 0 , 0 )]
if len ( c ) == 1 :
return [ c [ 0 ], ( 0 , 0 )]
return c
n = len ( nums )
return min ( n - ( n1 + n2 ) for a , n1 in get ( 0 ) for b , n2 in get ( 1 ) if a != b )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43 class Solution {
private int [] nums ;
private int n ;
public int minimumOperations ( int [] nums ) {
this . nums = nums ;
n = nums . length ;
int ans = Integer . MAX_VALUE ;
for ( int [] e1 : get ( 0 )) {
for ( int [] e2 : get ( 1 )) {
if ( e1 [ 0 ] != e2 [ 0 ] ) {
ans = Math . min ( ans , n - ( e1 [ 1 ] + e2 [ 1 ] ));
}
}
}
return ans ;
}
private int [][] get ( int i ) {
Map < Integer , Integer > freq = new HashMap <> ();
for (; i < n ; i += 2 ) {
freq . put ( nums [ i ] , freq . getOrDefault ( nums [ i ] , 0 ) + 1 );
}
int a = 0 ;
int n1 = 0 ;
int b = 0 ;
int n2 = 0 ;
for ( Map . Entry < Integer , Integer > e : freq . entrySet ()) {
int k = e . getKey ();
int v = e . getValue ();
if ( v > n1 ) {
b = a ;
n2 = n1 ;
a = k ;
n1 = v ;
} else if ( v > n2 ) {
b = k ;
n2 = v ;
}
}
return new int [][] {{ a , n1 }, { b , n2 }};
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 typedef pair < int , int > PII ;
class Solution {
public :
int minimumOperations ( vector < int >& nums ) {
int ans = INT_MAX ;
int n = nums . size ();
for ( auto & [ a , n1 ] : get ( 0 , nums ))
for ( auto & [ b , n2 ] : get ( 1 , nums ))
if ( a != b )
ans = min ( ans , n - ( n1 + n2 ));
return ans ;
}
vector < PII > get ( int i , vector < int >& nums ) {
unordered_map < int , int > freq ;
for (; i < nums . size (); i += 2 ) ++ freq [ nums [ i ]];
int a = 0 , n1 = 0 , b = 0 , n2 = 0 ;
for ( auto & [ k , v ] : freq ) {
if ( v > n1 ) {
b = a ;
n2 = n1 ;
a = k ;
n1 = v ;
} else if ( v > n2 ) {
b = k ;
n2 = v ;
}
}
return {{ a , n1 }, { b , n2 }};
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 func minimumOperations ( nums [] int ) int {
n := len ( nums )
get := func ( i int ) [][] int {
freq := make ( map [ int ] int )
for ; i < n ; i += 2 {
freq [ nums [ i ]] ++
}
a , n1 , b , n2 := 0 , 0 , 0 , 0
for k , v := range freq {
if v > n1 {
b , n2 , a , n1 = a , n1 , k , v
} else if v > n2 {
b , n2 = k , v
}
}
return [][] int {{ a , n1 }, { b , n2 }}
}
ans := 100000
for _ , e1 := range get ( 0 ) {
for _ , e2 := range get ( 1 ) {
if e1 [ 0 ] != e2 [ 0 ] && ans > ( n - ( e1 [ 1 ] + e2 [ 1 ])) {
ans = n - ( e1 [ 1 ] + e2 [ 1 ])
}
}
}
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 function minimumOperations ( nums : number []) : number {
const n = nums . length ,
m = 10 ** 5 ;
let odd = new Array ( m ). fill ( 0 );
let even = new Array ( m ). fill ( 0 );
for ( let i = 0 ; i < n ; i ++ ) {
let cur = nums [ i ];
if ( i & 1 ) {
odd [ cur ] = ( odd [ cur ] || 0 ) + 1 ;
} else {
even [ cur ] = ( even [ cur ] || 0 ) + 1 ;
}
}
let i1 = odd . indexOf ( Math . max (... odd ));
let i2 = even . indexOf ( Math . max (... even ));
if ( i1 != i2 ) {
return n - odd [ i1 ] - even [ i2 ];
} else {
let l1 = odd [ i1 ],
l2 = even [ i2 ];
( odd [ i1 ] = 0 ), ( even [ i2 ] = 0 );
let j1 = odd . indexOf ( Math . max (... odd ));
let j2 = even . indexOf ( Math . max (... even ));
return n - Math . max ( l1 + even [ j2 ], l2 + odd [ j1 ]);
}
}
GitHub