【LeetCode】80.Remove Dupliccates from Sorted Aray II解題報告（Python）

作者：负雪明ろうそくid：fuxuemingzhu個人ブログ：http://fuxuemingzhu.cn/
目次

テーマ記述

タイトルの大意

解題方法

日付

タイトルの住所:https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/description/
テーマの説明
Given a sorted array nums、remove the duplicates in-place such that duplicappares appared at at most twice and return the new length.
Do not allocate extra space for another array，you must do this by modifying the input array in-place with O(1)extra memory.
Example 1:

Given 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 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,1,2,3,3],

Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:
Confused why the returned value is an integer but your answer is an array？
Note that the input array is passed in by reference，which means modification to the input array will be known to the caler as.
Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

タイトルの大意
秩序配列中の出現回数が2を超えるものをフィルタリングし、そのまま操作します。
問題の解き方
その場の操作を見ると、普通は針を思い付きます。このテーマは二重の針が必要です。
最初に考えた二重針の操作方法は両端から中間に遍歴しています。そう考えると、後ろの数字が前の方に交換されていることに気づき、後の数字の出現回数を判断することができなくなりました。
問題は秩序化されていることに気づきました。この問題の正しいやり方は前からです。速い針はすべての数字を遍歴しています。もう一つの遅い針は問題の要求を満たさない第一の位置を指しています。このように、新しい数字を遍歴して、そしてこの新しい数字と遅いポインタが指す前の二つの数字を同時に交換して、この不満足な位置に交換して、二つのポインタを同時に右に移動すればいいです。
時間の複雑さはO（N）で、空間の複雑さはO（1）である。
コードは以下の通りです

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i = 0
        for n in nums:
            if i < 2 or n != nums[i - 2]:
                nums[i] = n
                i += 1
        return i

二ブラシは、より明確な二重ポインタを使用して、leftポインタは最初に判断すべき位置を指し、rightポインタは後の位置を指します。rightとleftが同じかどうかを判断して、rightとleftが待たない時まで、後ろのこの数字を前に移動すればいいです。

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        N = len(nums)
        if N <= 1: return N
        left, right = 0, 1
        while right < N:
            while right < N and nums[right] == nums[left]:
                right += 1
            left += 1
            if right < N:
                nums[left] = nums[right]
        return left

参考資料：
https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/discuss/27976/3-6-easy-lines-C++-Java-Python-Ruby
日付
2018年9月24日ーー皆さん中秋節おめでとうございます。2018年11月23日——これは金曜日ですか？