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 <= 1051 <= nums[i] <= 105
Solutions#
Solution 1#
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]);
}
}
|
