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]
, where2 <= i <= n - 1
.nums[i - 1] != nums[i]
, where1 <= 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
Solution: Greedy
Count and sort the frequency of numbers at odd and even positions.
Case 1: top frequency numbers are different, change the rest of numbers to them respectively.
Case 2: top frequency numbers are the same, compare top 1 odd + top 2 even vs top 2 even + top 1 odd.
Time complexity: O(nlogn)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua class Solution { public: int minimumOperations(vector<int>& nums) { const int n = nums.size(); if (n == 1) return 0; unordered_map<int, int> odd, even; for (int i = 0; i < n; ++i) ((i & 1 ? odd : even)[nums[i]])++; vector<pair<int, int>> o, e; for (const auto [k, v] : odd) o.emplace_back(v, k); for (const auto [k, v] : even) e.emplace_back(v, k); sort(rbegin(o), rend(o)); sort(rbegin(e), rend(e)); if (o[0].second != e[0].second) return n - o[0].first - e[0].first; int mo = o[0].first + (e.size() > 1 ? e[1].first : 0); int me = e[0].first + (o.size() > 1 ? o[1].first : 0); return n - max(mo, me); } }; |