26. 删除有序数组中的重复项 - 力扣(LeetCode)
题目:
给你一个 非严格递增排列 的数组 nums
,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums
中唯一元素的个数。
考虑 nums
的唯一元素的数量为 k
,你需要做以下事情确保你的题解可以被通过:
- 更改数组
nums
,使nums
的前k
个元素包含唯一元素,并按照它们最初在nums
中出现的顺序排列。nums
的其余元素与nums
的大小不重要。 - 返回
k
。
解题思路:
1. 原地删除 双引用思想:指针 fir、sec
2. 步骤解析:
(1)fir==sec,指向数组首元素
(2) sec向后移动,如果碰见与fir指向元素不相同的位置,此时fir进行移动。
这一步骤可以理解为:数组中的[0,fir]区间内存放的是不重复的元素,而sec就是负责去找不重复的元素的。一旦找到,fir就得在区间内为这个元素开辟空间,即fir++;
无论是否碰见重复元素,sec引用指针是一直往后移动的;
fir指向的元素就是删除后有效的最后一个元素,最后的有效元素个数就是fir指向的索引+1。
代码实现:
public int RemoveArrayElements(int[] nums){int fir=0,sec=0;//sec移动到元素的末尾,此时fir就指向最后一个不重复的元素//nums[0,fir]区间均为不重复元素while(sec<nums.length){if(nums[fir]!=nums[sec]){fir+=1;nums[fir]=nums[sec];}sec++;}return fir+1;}
思考:如果删除所有重复元素,如何进行改进?