山东省交通厅建设网站首页,河北城乡建设官方网站,深圳网站建设seo,google关键词排名1 题目描述 图1 题目描述 2 题目解读 对于有序数组nums#xff0c;要求在不使用额外数组空间的条件下#xff0c;删除数组nums中重复出现的元素#xff0c;使得nums中出现次数超过两次的元素只出现两次。返回删除后数组的新长度。
3 解法一#xff1a;双指针 双指针法可以…1 题目描述 图1 题目描述 2 题目解读 对于有序数组nums要求在不使用额外数组空间的条件下删除数组nums中重复出现的元素使得nums中出现次数超过两次的元素只出现两次。返回删除后数组的新长度。
3 解法一双指针 双指针法可以很好地解决此题。
3.1 解题思路 设置双指针从数组nums的第3个元素开始比较直到nums的最后一个元素。
3.2 设计代码
#include iostream
#include vector
using namespace std;
class Solution {
public:int removeDuplicates(vectorint nums) {int n nums.size();if (n 2) {return n;}int slow 2, fast 2;while (fast n) {if (nums[slow - 2] ! nums[fast]) {nums[slow] nums[fast];slow;}fast;}return slow;}
};
int main() {int x[] { 1,1,1,2,2,3 };vectorint nums;for (int i 0; i 6; i){nums.push_back(x[i]);}Solution S;int ans S.removeDuplicates(nums);cout ans endl;return 0;
}3.3 复杂度分析
时间复杂度。while循环遍历了一遍数组元素。空间复杂度。没有使用额外数组空间。
3.4 提交结果 图2 双指针法代码执行结果 4 解法二前移法 前移法是由双指针法扩展出来的一种方法与双指针法有着相似的思想。
4.1 解题思路 设置指针right从数组nums的第3个元素开始遍历使用变量k记录需要移除的元素的个数将需要移动的元素前移k个位置。
4.2 设计代码
#include iostream
#include vector
using namespace std;
class Solution {
public:int removeDuplicates(vectorint nums) {int n nums.size();if (n 2) {return n;}// k累计删除的元素个数int fast 2, k 0;while (fast n) {if (nums[fast - k - 2] ! nums[fast]) {nums[fast - k] nums[fast];}else {k;}fast;}return fast - k;}
};
int main() {int x[] { 1,1,1,2,2,3 };vectorint nums;for (int i 0; i 6; i){nums.push_back(x[i]);}Solution S;int ans S.removeDuplicates(nums);cout ans endl;return 0;
}4.3 复杂度分析
时间复杂度。while循环遍历了一遍数组nums的元素。空间复杂度。没有使用额外数组空间。
4.4 提交结果 图3 前移法代码执行结果 5 解题心得
让有序数组nums中重复出现的元素只出现两次是让其只出现一次的变体题目难度更大。双指针法与前移法之间可以相互转换。双指针法中left指针用于放置新元素。
