day2【代码随想录】移除元素

---

一、移除数据元素

一个数组 nums 和一个值 val，需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。不需要考虑数组中超出新长度后面的元素。

1、暴力求解

两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。
暴力解法的时间复杂度是O(n^2)

class Solution {
    public int removeElement(int[] nums, int val) {
        int j=0;
        int size = nums.length;
        for(int i = 0; i<nums.length;i++){
            if(val==nums[i]){
                for(j = i+1;j<nums.length;j++){
                    nums[j-1]=nums[j];
                }
                i--;
                size--;
            }
        }
        return size;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2、双指针法

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作
定义快慢指针：

快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
慢指针：指向更新 新数组下标的位置

class Solution {
    public int removeElement(int[] nums, int val) {
        int fastIndex=0;
        int slowIndex=0;
        for(fastIndex=0;fastIndex<nums.length;fastIndex++){
            if(nums[fastIndex]!=val){
                nums[slowIndex++]=nums[fastIndex];
            }
        }
        return slowIndex;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

3、相向双指针法

class Solution {
    public int removeElement(int[] nums, int val) {
        int leftIndex=0;
        int rightIndex=nums.length-1;
        while(rightIndex>=0 && nums[rightIndex]==val){
            rightIndex--;
        }
        while(leftIndex<=rightIndex){
            if(nums[leftIndex]==val){
                //交换
                nums[leftIndex]=nums[rightIndex];
                rightIndex--;
            }
            leftIndex++;
            while(rightIndex>=0 && nums[rightIndex]==val){
                rightIndex--;
            }
        }
        return leftIndex;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

二、删除有序数组中的重复项

给一个升序排列的数组 nums ，请原地删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。元素的相对顺序应该保持 一致 。
利用双指针法求解：

class Solution {
    public int removeDuplicates(int[] nums) {
        int slowIndex = 0;
        int fastIndex = 1;
        for(fastIndex=1;fastIndex<nums.length;fastIndex++){
            if(nums[slowIndex]!=nums[fastIndex]){
                nums[++slowIndex]=nums[fastIndex];
            }
        }
        return slowIndex+1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

三、删除有序数组中的重复项II

给一个有序数组 nums ，请原地删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
利用双指针法求解：

class Solution {
    public int removeDuplicates(int[] nums) {
        int slowIndex = 0;
        int fastIndex = 1;
        int count=1;
        for(fastIndex=1;fastIndex<nums.length;fastIndex++){
            if(nums[slowIndex]==nums[fastIndex] && count<2){
                count++;
                nums[++slowIndex]=nums[fastIndex];
            }else if(nums[slowIndex]!=nums[fastIndex]){
                count=1;
                nums[++slowIndex]=nums[fastIndex];
            }
        }
        return slowIndex+1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

四、移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。

采用相向双指针法求解：

class Solution {
    public void moveZeroes(int[] nums) {
        int leftIndex=0;
        int rightIndex=nums.length-1;
        while(rightIndex>=0 && nums[rightIndex]==0)
            rightIndex--;
        while(leftIndex<=rightIndex){
            if(nums[leftIndex]==0){
                //交换
                int temp;
                temp=nums[rightIndex];
                nums[rightIndex]=nums[leftIndex];
                nums[leftIndex]=temp;
            }
            else
                leftIndex++;
            while(rightIndex>=0 && nums[rightIndex]==0){
                rightIndex--;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

不满足题目要求：

改变了非零元素的相对位置。
采用双指针法：
不改变元素的位置，先将非零元素放入。剩下的位置补零即可

class Solution {
    public void moveZeroes(int[] nums) {
        int slowIndex=0;
        int fastIndex=0;
        for(fastIndex=0;fastIndex<nums.length;fastIndex++){
            if(nums[fastIndex]!=0){
                nums[slowIndex++]=nums[fastIndex];
            }
        }
        for(int i=slowIndex;i<nums.length;i++){
            nums[i]=0;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14