Remove Duplicates from Sorted Array II

描述

Follow up for "Remove Duplicates": What if duplicates are allowed at most twice?

For example, given sorted array A = [1,1,1,2,2,3], your function should return length = 5, and A is now [1,1,2,2,3]

分析

加一个变量记录一下元素出现的次数即可。这题因为是已经排序的数组，所以一个变量即可解决。如果是没有排序的数组，则需要引入一个 hashmap 来记录出现次数。

代码 1

Python

# Remove Duplicates from Sorted Array II
# Time complexity: O(n), Space Complexity: O(1)
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        N = 2
        if len(nums) <= N:
            return len(nums)

        slow = N
        for fast in range(N, len(nums)):
            if nums[fast] != nums[slow-N]:
                nums[slow] = nums[fast]
                slow += 1

        return slow

Java

// Remove Duplicates from Sorted Array II
// Time complexity: O(n), Space Complexity: O(1)
public class Solution {
    public int removeDuplicates(int[] nums) {
        final int N = 2;
        if (nums.length <= N) return nums.length;

        int slow = N;
        for (int fast = N; fast < nums.length; fast++){
            if (nums[fast] != nums[slow - N])
                nums[slow++] = nums[fast];
        }

        return slow;
    }
};

C++

// Remove Duplicates from Sorted Array II
// Time complexity: O(n), Space Complexity: O(1)
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        const int N = 2;
        if (nums.size() <= N) return nums.size();

        int slow = N;
        for (int fast = N; fast < nums.size(); fast++){
            if (nums[fast] != nums[slow-N])
                nums[slow++] = nums[fast];
        }

        return slow;
    }
};

代码 2

下面是一个更简洁的版本。上面的代码略长，不过扩展性好一些，例如将occur < 2改为occur < 3，就变成了允许重复最多 3 次。

Java

// Remove Duplicates from Sorted Array II
// Time Complexity: O(n), Space Complexity: O(1)
public class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        int index = 0;
        for (int i = 0; i < n; ++i) {
            if (i > 0 && i < n - 1 && nums[i] == nums[i - 1] && nums[i] == nums[i + 1])
                continue;

            nums[index++] = nums[i];
        }
        return index;
    }
};

C++

// Remove Duplicates from Sorted Array II
// Time Complexity: O(n), Space Complexity: O(1)
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        const int n = nums.size();
        int index = 0;
        for (int i = 0; i < n; ++i) {
            if (i > 0 && i < n - 1 && nums[i] == nums[i - 1] && nums[i] == nums[i + 1])
                continue;

            nums[index++] = nums[i];
        }
        return index;
    }
};

相关题目

• Remove Duplicates from Sorted Array
• Remove Element
• Move Zeroes
• Remove Duplicates from Sorted List