27. 移除元素

双指针法

class Solution {
    public int removeElement(int[] nums, int val) {

        /**
         * 使用双指针从两端遍历，start指向当前遍历元素，end指向最后一个待换元素
         * 当遇到目标元素时，和最后一个元素互换
         * 头指针等于尾指针时结束循环
         */
        if (nums == null || nums.length == 0){
            return 0;
        }

        int start = 0;
        int end = nums.length - 1;
        int temp = 0;

        while (start < end){

            if (nums[start] == val){

                temp = nums[start];
                nums[start] = nums[end];
                nums[end] = temp;
                end--;
            }
            else {
                start++;
            }
        }

        /**
         * 最后要判断最后停留的位置是否是目标元素，如果是的话就要舍弃
         * 因为要加1，为了避免end + 1边界溢出，让start + 1
         */
        if (nums[start] != val){
            return start + 1;
        }
        else {
            return start;
        }
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */

优化2——不使用额外空间、合并数组为空的情况且简化返回值

class Solution {
    public int removeElement(int[] nums, int val) {

        /**
         * 使用双指针从两端遍历，start指向当前遍历元素，end指向最后一个待换元素
         * 当遇到目标元素时，让最后一个元素直接覆盖
         * 头指针大于尾指针时结束循环
         */
        int start = 0;
        int end = nums.length - 1;

        while (start <= end){

            if (nums[start] == val){

                nums[start] = nums[end];
                end--;
            }
            else {
                start++;
            }
        }

        /**
         * start就是剩余数组元素的个数
         */
        return start;
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */

https://leetcode-cn.com/problems/remove-element/