卖萌的弱渣

I am stupid, I am hungry.

Remove Duplicates From Sorted Array 2

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

Example

Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn’t matter what you leave beyond the new length.

Solution

  • Java: Best Solution
(Remove-Duplicates-from-Sorted-Array2.java) download
1
2
3
4
5
6
7
8
9
10

public class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0;
        for(int num: nums){
            if(i<2 || num > nums[i-2])
                nums[i++] = num;
        }
        return i;
    }
}
(Remove-Duplicates-from-Sorted-Array2.py) download
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

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        if nums == None or len(nums) == 0:
            return 0

        start = 0
        # first element nums[end] != nums[start]
        end = 0
        index = 0

        while start < len(nums):
            end = self.findRec(nums,start)
            nums[index] = nums[start]
            index += 1
            if end - start >= 2:
                nums[index] = nums[start]
                index += 1
            start = end
        return index


    def findRec(self, nums, start):
        while start + 1 < len(nums):
            if nums[start] != nums[start+1]:
                return start+1
            start += 1
        return start+1