长大后想做什么？做回小孩！

0%

LeetCode——移除元素

发表于 更新于 分类于 Valine：
本文字数： 590

NO.27 移除元素 简单

lK1La6.png

lK1qVx.png

思路一：双指针法 这道题和第26题如出一辙，题目中的关键点也一样。算法的区别在于对数组第一个元素的处理，26题中第一个元素是不需要”覆盖”的，但是本题的第一个元素有可能需要进行”覆盖”。

用两个指针i和j同时指向0号元素，如果j号指针不等于val，就先将j号元素”覆盖”i号元素再移动i指针，如果j号元素等于val则移动j指针，循环直至j指针遍历完所有元素。

1
2
3
4
5
6
7
8
9
10
11
12
public int removeElement(int[] nums, int val) {
        if (nums==null||nums.length==0)return 0;
        int i=0;
        for (int j=0;j<nums.length;j++){
//            如果j号指针不等于val，就先将j号元素"覆盖"i号元素再移动i指针
            if (nums[j]!=val){
                nums[i]=nums[j];
                i++;
            }
        }
        return i;
    }

时间复杂度：O(n)

思路二：优化双指针法 思路一有一个很明显的弊端，当数组元素和val相等的元素很少时，依然需要移动很多数组元素，例如{[1,2,3,4,5]，val=4}这组输入中”1,2,3”并不需要移动，但是依然会进行自身赋值操作；亦或是{[1,2,3,4,5]，val=1}只需要将5覆盖到1的位置即可，但是思路一的算法并不是这样的。

真对上述出现的问题，对思路一进行优化：1. 双指针i和j分别等于0和nums.length。2. 当i指向的元素等于val时，就先让j-1指向的元素覆盖i指向的元素再进行j–移动。3. 如果i指向元素不等于val，就进行i++移动。4. 循环直至i>=j。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int removeElement(int[] nums, int val) {
    if (nums==null||nums.length==0)return 0;
    int i=0,j=nums.length;
    while (i<j){
        if (nums[i]==val){
            nums[i]=nums[j-1];
            j--;
        }else {
            i++;
        }
    }
    return j;
}

时间复杂度：O(n)，i和j最多遍历j步。在这个方法中，赋值操作的次数等于要删除的元素的数量。因此，如果要移除的元素很少，效率会更高。

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github