LeetCode #27 移除元素

思路讲解

一种思路是可以新建一个数组。然后，遍历原数组，将所有值不等于val的元素放入新建的数组中，之后再将新建数组中那些值不等于val的元素拷贝至原数组。

public int removeElement(int[] nums, int val) {    // 新建数组，用于存放原数组中值不等于val的元素    int[] arr = new int[nums.length];
    // 新建数组中存放了多少个原数组中值不等于val的元素    int j = 0;    // 遍历原数组，将值不等于val的元素放入数组arr中    for(int i = 0; i < nums.length; i++) {        if (nums[i] != val) {            arr[j] = nums[i];            j++;        }    }
    // 拷贝数组arr中的数据到原数组中    for(int m = 0; m < j; m++) {        nums[m] = arr[m];    }    return j;}

但题目中要求原地移除所有数值等于val的元素，因此上面的实现方式是与题意不符的，接下来我们就以示例中的数组{3, 2, 2, 3}为例来看下如何原地移除所有数值等于val的元素。

首先，定义变量j，我们规定在区间[0,j)中的元素都是值不等于val=3的元素。

接着，遍历原数组，对其中的每一个元素和val=3进行比较。比较的结果，有两种情况。一是，当前考察的元素值等于val=3；二是，当前考察的元素值不等于val=3。

对于第一种情况，如下图所示，当前考察的元素为变量i指向的元素3，其值与val相等。

对于这种情况，要做的就是继续考察下一个元素，即变量i向后移动一个位置(i++)。

此时，变量i指向的元素2不等于val=3。

对于这种情况，首先要做的是将变量i所指向的元素值赋予变量j所指向的元素所在位置，即nums[j]=nums[i]。

接着要做的就是将变量j向后移动一个位置，即j++。

对于数组nums中剩余的元素2和3，重复上述步骤，即可将所有数值等于val的元素移除。

代码实现

public int removeElement(int[] nums, int val) {    // 定义变量j，在区间[0,j)中的元素都是值不等于val的元素    int j = 0;    for(int i = 0; i < nums.length; i++) {        // 如果当前考察的元素其值不等于val        // 则将当前元素放入区间[0,j)中        if (nums[i] != val) {            nums[j] = nums[i];            // 在将当前元素放入区间[0,j)中后，j++            j++;        }    }    return j;}

更多相关文章

随机推荐