您现在的位置是:首页 >其他 >算法第一天——移除元素网站首页其他

算法第一天——移除元素

weixin_45914112 2024-06-17 11:19:03
简介算法第一天——移除元素

常用方法

  • 暴力破解(费时间,效率低)
  • 快慢指针(双指针)

题目

1、移除元素
暴力破解思路:

  1. 使用两个for循环嵌套
  2. 第一个循环顺序遍历数组
  3. 当nums[i]==val 的时候 ,执行第二层循环,将后面的值覆盖前面的值。
  4. 执行第二个循环
  5. 被覆盖掉的值之后,下标要减1.( 因为下标i以后的数值都向前移动了一位,所以i也向前移动一位)
  6. 此时数组的大小-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;
    }
}
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。