LeetCode //80. Remove Duplicates from Sorted Array II-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode //80. Remove Duplicates from Sorted Array II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

80. Remove Duplicates from Sorted Array II

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = […]; // Input array
int[] expectedNums = […]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7, nums = [0,0,1,1,2,3,3,,]
Explanation: Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

$1 <= nums.length <= 3 * 10^4$
$10^4 <= nums[i] <= 10^4$
nums is sorted in non-decreasing order.

From: LeetCode
Link: 80. Remove Duplicates from Sorted Array II文章来源地址https://www.toymoban.com/news/detail-535494.html

Solution:

Ideas：

In this function, we start by checking if the array has less than or equal to 2 elements. If it does, we return numsSize since all elements are unique or appear at most twice.

Next, we initialize i and j to 2. We then start a loop that runs from i to numsSize - 1. Inside the loop, we check if the current element is different from the element at position j-2. If it is, we place it at the position pointed to by j and increment j.

Finally, we return j, which is the number of elements in the array after removing duplicates that appear more than twice.

This function modifies the array in-place and does not use any extra space, except for a few variables. The time complexity is O(n), where n is the size of the array.

Code:

int removeDuplicates(int* nums, int numsSize){
    if(numsSize <= 2) return numsSize;

    int i, j = 2;
    for(i = 2; i < numsSize; i++){
        if(nums[i] != nums[j-2]){
            nums[j] = nums[i];
            j++;
        }
    }

    return j;
}

到了这里，关于LeetCode //80. Remove Duplicates from Sorted Array II的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

LeetCode //80. Remove Duplicates from Sorted Array II