Python|“双指针法”解删除数组重复项问题

问题描述

Python算法题目中，掌握一定的方法和技巧或者说是了解基础解题规律，能够在解决更多复杂问题的过程中思路更清晰，算法更简单易懂。接下来用一个leetcode题目“原地删除排序数组重复项”的案例来介绍一下“双指针法”的具体应用。

题目描述：

给定一个排序数组，需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后新的数组。

输入：[1,1,2]

输出：[1,2]

解决方案

1.首先需要引入两个指针i，k；

2.指针i先用于遍历数组，由于要删除相同数字，需要判断是否与上一个数字相同，当遇到nums[i] != nums[i-1]时，说明已遇到新的不同数字，此时，将该数字记录；

3.指针k有两个不同的作用。

一是用来统计这个数组中不同数字的数量，即每当遇到新的数字时，就执行k +=1 ；

二是为了记录这个新的数字，将指针i遍历而遇到的新的数字的索引赋值给k，即nums[k] = nums[i]。

4.最终得到的k就是返回值。

代码示例：

class Solution:
    def removeDuplicates(self,  nums: [int]) -> int:
        if len(nums)  == 0: return 0
        k =  1
        for  i in range(1, len(nums)):
             if nums[i] != nums[i - 1]:
                 nums[k] = nums[i]
                 k += 1
         return k 

结语

通过这道题目，可以了解到在解决原地删除问题时，遇到这种有序依次排列的数组，用遍历来做十分方便，而遍历数组，就联想到可以用双指针法来解决。两个指针，一个用来遍历判断，一个用来记录数据，十分容易就能得到结果。