您现在的位置是:首页 >其他 >算法第一天——移除元素网站首页其他
算法第一天——移除元素
简介算法第一天——移除元素
常用方法
- 暴力破解(费时间,效率低)
- 快慢指针(双指针)
题目
1、移除元素
暴力破解思路:
- 使用两个for循环嵌套
- 第一个循环顺序遍历数组
- 当nums[i]==val 的时候 ,执行第二层循环,将后面的值覆盖前面的值。
- 执行第二个循环
- 被覆盖掉的值之后,下标要减1.( 因为下标i以后的数值都向前移动了一位,所以i也向前移动一位)
- 此时数组的大小-1
class Solution {
public int removeElement(int[] nums, int val) {
int size = nums.length;
for(int i = 0; i<nums.length; i++){
if(nums[i]==val){
for(int j = i+1;j<size;j++){
nums[j-1]=nums[j];
}
}
i--;
size--;
}
return size;
}
}
快慢指针思路
双指针法(快慢指针法): 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
定义快慢指针
- 快指针:寻找新数组的元素 ,新数组就是不含有目标元素的数组
- 慢指针:指向更新 新数组下标的位置
- 定义一个慢指针、一个快指针。
- 快指针先走,如果不等于val,则将快指针所指的值赋值给慢指针。
- 然后慢指针的值+1;从而去掉重复的目标值。得到移除元素后的数组长度。
class Solution {
public int removeElement(int[] nums, int val) {
// (2)使用快慢指针
int slowPoint = 0;
for(int fastPoint = 0; fastPoint<nums.length; fastPoint++){
if(nums[fastPoint] != val){
nums[slowPoint] = nums[fastPoint];
slowPoint++;
}
}
return slowPoint;
}
}
相似题目:
- 26.删除排序数组中的重复项
- 283.移动零
- 844.比较含退格的字符串
- 977.有序数组的平方
26.删除排序数组中的重复项
题解:
class Solution {
public int removeDuplicates(int[] nums) {
if(nums == null || nums.length ==1) return nums.length;
// 快慢指针
// 定义一个慢指针,用于更新
int slowPoint = 0;
int fastPoint = 0;
// 定义一个快指针,用于遍历
while( fastPoint<nums.length){
if(nums[fastPoint] == nums[slowPoint]){
fastPoint++;//如果相同就跳过,寻找下一个值
}else{
//如果不相同,就将慢指针+1,将不同的值,复制给slowPoint+1的位置。
slowPoint++;
nums[slowPoint]=nums[fastPoint];
fastPoint++;
}
}
return slowPoint+1;
}
}
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。