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

原创
08/26 00:00
阅读数 0

本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。

问题描述

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


结语

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





编辑:王楠岚

稿件来源:深度学习与文旅应用实验室(DLETA)

本文分享自微信公众号 - 算法与编程之美(algo_coding)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部