Remove element问题的简单优化

原题链接: Remove Element. 这是一道easy的水题,之所以拿出来讲,主要是其中有一个巧妙的小优化,可以因小见大体会到代码效率优化的无处不在,激励自己写出最优的代码.

最初解法

public class Solution {
    public int removeElement(int[] nums, int val) {
        int length = nums.length;
        int res = 0;
        for(int i=0; i<length; ++i) {
            if (nums[i] != val) {
                 nums[res] = nums[i];
                 res++;
            }
        }
        return res;
    }
}

思路讲解: 从头开始遍历数组元素length次,当元素nums[i]与val不相等,重新赋值, 相等则跳过,最终数组中前res个元素都是不等于val的元素

效率:

改进解法

public class Solution {
    public int removeElement(int[] nums, int val) {
        int length = nums.length;
        int res = 0;
        // 减少i++操作引发70%的效率提升
        for(int i=0; i<length-res;) {
            if (nums[i] == val) {
                 nums[i] = nums[length-res-1];
                 res++;
            } else {
                i++;
            }
        }
        return length-res;
    }
}

思路讲解: 从头开始遍历数组元素length-res次,当元素nums[i]与val相等,i不改变, 从末尾取出一个对应的将不再被循环遍历到的元素赋值到当前的nums[i], 再次与val比较;如果nums[i]与val不相等则i++,比较下一元素

效率: