本文主要是介绍【python】删除有序数组中的重复项(快慢指针),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
python系列文章目录
【python】基于cv2提取图片上的文本内容
【python】简单作图
【python】数组字符串等实用
【python】sort与sorted排序使用
【python】对角线遍历
【python】岛屿数量
【python】删除有序数组中的重复项
- python系列文章目录
- 力扣说明
- 1.分析
- 2.逻辑分析
- 2.1 遍历
- 2.2 指针变化
- 2.3 输出
- 3.代码实现
力扣说明
给你一个非严格递增排列的数组 nums ,请你原地删除重复出现的元素,使每个元素只出现一次 ,返回删除后数组的新长度。元素的相对顺序应该保持一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过:
更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。返回 k 。
示例 :
输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]
解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
1.分析
对于示例1这个数组,需要原地修改这个数组。
我们定义慢指针 l e f t left left和快指针 r i g h t right right, l e f t left left用于保存非重复的数据, r i g h t right right用于判断后面的数据是否与 l e f t left left重复。
2.逻辑分析
2.1 遍历
当 r i g h t right right遍历到数组长度 l e n g t h length length的时候结束,即:
while right < length
2.2 指针变化
对于 r i g h t right right,每次的判断都需要+1;
对于 l e f t left left,只有当后面 n u m s [ r i g h t ] ! = n u m s [ l e f t ] nums[right]!=nums[left] nums[right]!=nums[left]时,说明 n u m s [ r i g h t ] nums[right] nums[right]需要往前移动,即把 l e f t + 1 left+1 left+1,并把 n u m s [ r i g h t ] nums[right] nums[right]赋值给 n u m s [ l e f t ] nums[left] nums[left]
if nums[left] == nums[right]:right += 1
else:left += 1nums[left]=nums[right]
2.3 输出
本题目主要考察原地修改,并输出不重复元素的个数,即最终的 l e f t + 1 left+1 left+1
3.代码实现
class Solution:def removeDuplicates(self, nums: List[int]) -> int:length = len(nums)left = 0right = 0while right < length:if nums[left] == nums[right]:right += 1else:left += 1nums[left]=nums[right]return left + 1
这篇关于【python】删除有序数组中的重复项(快慢指针)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!