排序｜ Leetcode 27

Leetcode 分类刷题 —— 排序类（Sort）

1、题目

Leetcode 27. Remove elements 移除元素

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

2、思路

双指针解法：左右指针分别向中间移动：
若左指针值与val相同，则与右指针值进行交换，再检查一下交换来的值是不是等于val；
若左指针值与val不同，则左指针向右移动。

时间复杂度: O(n) 只需遍历一次数组
空间复杂度: O(1)

3、 java 代码

class Solution {
    public int removeElement(int[] nums, int val) {
        int j = nums.length - 1;
        for (int i = 0; i <= j; i++) {
            if (nums[i] == val) {
                // i-- 检查交换后的 nums[i] 是否还为 val
                swap(nums, i--, j--);
            }
        }
        return j + 1;
    }
    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    // 方法二
    // 定义一个方法，接受一个整型数组nums和一个整型值val作为参数
    public int removeElement2(int[] nums, int val) {
        // 初始化一个变量k，用来记录数组中不等于val的元素的个数
        int k = 0;
        // 遍历数组
        for (int i = 0; i < nums.length; i++) {
            // 如果当前元素不等于val
            if (nums[i] != val) {
                // 将其复制到数组的前k个位置
                nums[k] = nums[i];
                // 将k加一
                k++;
            }
        }
        // 返回k作为最终结果
        return k;
    }
}