Leetcode 27. Remove Element(删除元素)

题意重述

从数组中删除指定元素并返回数组长度,无需再申请内存空间,要求时间复杂度O(n),空间复杂度O(1) 原题链接

解题思路

类似快慢指针的原理,设置两个相同的游标i,j,i用于遍历整个数组,与指定元素不相等时i,j同时自增,与指定元素相等时j保持不变,每一次遍历都将i位置赋值给j位置,这样在任何时候i,j的间隔就是之前需要删除元素的总和,最后j就是删除元素后数组的长度

代码示例

#include<bits/stdc++.h> using namespace std; class Solution { public: int removeElement(int nums[], int val, int length) { int j=0; for(int i=0;i<length;i++) { if(val==nums[i]) { continue; } nums[j]=nums[i]; j++; } return j; } }; int main() { int a[] = {2, 0, 1, 7, 2, 0, 1, 8, 2 ,0 ,1 , 9} ; cout<<"Before Delete:"<<endl; for(int i=0; i<9; i++) { cout<<a[i]<<" " ; } cout<<endl; Solution solution; int rm = solution.removeElement(a, 2, 9); cout<<"After Delete:"<<endl; for(int i=0; i<rm; i++) { cout<<a[i]<<" " ; } cout<<endl; cout<<"length: "<< rm <<endl; return 0; }

输出示例

Before Delete:
2 0 1 7 2 0 1 8 2 
After Delete:
0 1 7 0 1 8 
length: 6

发表评论

电子邮件地址不会被公开。 必填项已用*标注