Day1

1 删除有序数组中的重复项[T26]

伪代码

\begin{algorithm} \caption{removeDuplicates(A)} \begin{algorithmic} \State slow=0 \For{fast=1 \To A.length-1} \State \If{A[fast]!=A[slow]} \State A[slow+1] = A[fast] \State slow += 1\EndIf\EndFor \end{algorithmic} \end{algorithm}

Python

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        """
        快慢指针法快指针遍历数组，慢指针指向一元素的第一个值
        """
        # 当数组长度为1时直接返回即可
        if len(nums) == 1:
            return 1
        slow = 0
        for fast in range(1, len(nums)):
            if nums[slow] != nums[fast]:
                slow += 1
                nums[slow] = nums[fast]
        return slow + 1
        # 时间复杂度O(n)；空间复杂度O(1)

C++

int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        int slow = 0;
        for (int fast=1; fast<nums.size(); fast++){
            if (nums[fast]!=nums[slow]){
                nums[++slow] = nums[fast];
            }
        }
        return slow+1;
    }

解决方法及证明

双指针fast, slow

• fast:用以跳过重复序列并遍历整个数组
• slow:用以指向最后合法元素位置

1. 初始化：当slow在 \(0\) 处, fast在1处
2. 保持：当出现首个与目前slow不同的元素时，slow向前移动并赋值为fast所在元素，此时slow及其以前的子集符合要求。
3. 结束：当fast达到数组尾部时，迭代停止，此时slow及其以前的子集符合要求。

2 删除有序数组中的重复项Ⅱ[T80]

伪代码

\begin{algorithm} \caption{removeDuplicates2(A)} \begin{algorithmic} \State \IF{A.length<=2} \State \Return A.length \EndIf \State slow=1 \State \For{fast=2\To A.length} \State \If{A[fast]!=A[slow-1]} \State slow += 1 \State A[slow] = A[fast] \EndIf \EndFor \State \Return slow+1 \end{algorithmic} \end{algorithm}

Python

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        """
        快慢指针法，快指针用于遍历一遍数组，慢指针指向目前遍历过程中某元素符合规则的最后一个
        """
        if len(nums) <= 2:
            return len(nums)
        slow = 1
        for fast in range(2, len(nums)):
            if nums[fast] != nums[slow] or nums[fast] != nums[slow-1]:  # 首先若与目前的slow不同则符合规则，进一步；若与目前相同但是与slow的前一个不同，那同样可以进一步
                slow += 1
                nums[slow] = nums[fast]
        return slow + 1
        # 时间复杂度：O(n)；空间复杂度：O(1)

C++

int removeDuplicates(vector<int>& nums) {
        if (nums.size()<=2){
            return nums.size();
        }
        int slow = 1;
        for (int fast=2; fast<nums.size(); fast++){
            if (nums[fast]!=nums[slow-1]){
                nums[++slow]=nums[fast];
            }
        }
        return slow+1;
    }

解决方法及证明

双指针，fast和slow：

• fast：用以遍历全数组的同时跳出重复值
• slow：用以记录合法子集的最后一个索引

循环不变式：slow及其以前元素组成的子集是满足要求，且其中的元素是原数组各数值出现的前两个而非其他位置的。

1. 初始化：初始的slow=1即数组的前两个元素组成的子集必然满足条件。

2. 保持：需分情况讨论，slow向前走的情况分为：1)首次添加一个元素;2)重复添加一个已经出现一次的元素。

   • 当首次添加时，slow及其以前的元素构成的子集一定满足条件（假设），此时slow-1为其他元素，在slow+1首次添加元素，且下次增加相同元素的时机是当fast来到原数组相同元素第二次出现的位置，而非其他位置，故保持循环不变式成立；
   • 当重复添加时，易得也满足，且下一次不会再重复添加第三次因为此时slow-1为该元素，不会导致slow的更新(A[fast]!=A[slow-1])，循环不变式成立。

3. 终止：当fast达到原数组的末尾时循环终止，此时不会再添加相同的元素和首个元素，循环不变式易得成立。