You are given a 0-indexed integer array nums
. The array nums
is beautiful if:
nums.length
is even.nums[i] != nums[i + 1]
for alli % 2 == 0
.
Note that an empty array is considered beautiful.
You can delete any number of elements from nums
. When you delete an element, all the elements to the right of the deleted element will be shifted one unit to the left to fill the gap created and all the elements to the left of the deleted element will remain unchanged.
Return the minimum number of elements to delete from nums
to make it beautiful.
Example 1:
Input: nums = [1,1,2,3,5] Output: 1 Explanation: You can delete eithernums[0]
ornums[1]
to makenums
= [1,2,3,5] which is beautiful. It can be proven you need at least 1 deletion to makenums
beautiful.
Example 2:
Input: nums = [1,1,2,2,3,3] Output: 2 Explanation: You can deletenums[0]
andnums[5]
to make nums = [1,2,2,3] which is beautiful. It can be proven you need at least 2 deletions to make nums beautiful.
Constraints:
1 <= nums.length <= 105
0 <= nums[i] <= 105
Solution: Greedy + Two Pointers
If two consecutive numbers are the same, we must remove one. We don’t need to actually remove elements from array, just need to track how many elements have been removed so far.
i is the position in the original array, ans is the number of elements been removed. i – ans is the position in the updated array.
ans += nums[i – ans] == nums[i – ans + 1]
Remove the last element (just increase answer by 1) if the length of the new array is odd.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua class Solution { public: int minDeletion(vector<int>& nums) { const int n = nums.size(); int ans = 0; for (int i = 0; i - ans + 1 < n; i += 2) ans += nums[i - ans] == nums[i - ans + 1]; ans += (n - ans) & 1; return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment