LeetCode #80 删除排序数组中的重复项II

思路讲解题目要求排序数组中的重复元素最多出现两次。因此，我们要知道一个元素的出现次数，那怎么知道一个元素的出现次数呢？可以通过找到下一个和当前考察元素值不同的元素位置，然后用其索引值减去当前考察元素的索引值，结果就是当前元素在数组中的出现次数。如下图，变量i所指向的元素为当前考察的元素，其索引值为0。变量k所指向的元素为下一个和当前考察元素值不同的元素，其索引值为3。两者之差为3，即当前考察的元素1在数组中共出现3次。在知道当前考察元素的出现次数后，接着要做的就是看其出现次数是否大于两次。如果当前考察的元素出现次数小于等于2，则其在结果数组中出现次数不变；如果当前考察的元素出现次数大于2，则其在结果数组中出现次数为2次。在确定当前考察元素，在结果数组中应该出现的次数，并将其存入结果数组中之后，接下来要做的就是继续考察下一个元素，即和当前考察元素值不等的元素。以上是对整体思路的梳理，接下来以数组{1, 1, 1, 2, 2, 3}为例来看下具体过程。首先，定义变量j，其初始值为0，区间[0,j)表示移除重复元素后，结果数组中的元素。变量i的初始值也为0，指向当前考察的元素。接着，查找第一个和当前所考察元素值不相等的元素，用变量k表示。在数组{1, 1, 1, 2, 2, 3}中和当前考察元素1不相等的第一个元素是2。根据上面整体思路讲解的，当前考察的元素1出现次数为3次，即变量k的值减去变量i的值。接着要做的就是将变量i所指向的元素1复制两个到结果数组中，因为重复元素最多出现2次。每次在将变量i指向的元素复制到结果数组中后，变量j向后移动一个位置。

接着考察下一个元素。将变量k的值赋予变量i，即变量i移到变量k所在的位置。
此时变量i所指向的元素2为当前考察的元素，重复上述过程，即可将排序数组中重复的元素移除，使其最多出现两次。
动画演示上述思路的代码实现如下：

public int removeDuplicates(int[] nums) {    int[] resNums = new int[nums.length];
    // 定义变量j，其初始值为0，    // 区间[0,j)表示移除重复元素后，结果数组中的元素    int j = 0;
    // 当前考察的元素    int i = 0;    while (i < nums.length) {        // 查找下一个和当前元素值不相等的元素的下标        int k = nextDifferentNum(i, nums);
        // k-j的值表示当前考察的元素出现的次数        // 而题目要求每个元素最多出现2次        // 因此，需要将k-j的值和2比较，取两者最小值        // 即curNumCount值最大为2        int curNumCount = Math.min(2, k - i);
        // 将当前考察的元素最多只保存2个        for(int n = 0; n < curNumCount; n++) {            // i+n表示当前考察元素应放在数组的哪个位置            resNums[j] = nums[i];            j++;        }
        // 更新i的值为下一个和其值不相等的元素的索引值        // 即下一个要考察的元素        i = k;    }
    // 将结果数组中的元素复制到原数组    for(int r = 0; r < j; r++) {        nums[r] = resNums[r];    }
    return j;}
private int nextDifferentNum(int index, int[] nums) {    for(int m = index; m < nums.length; m++) {        if (nums[m] != nums[index]) {            return m;        }    }    return nums.length;}

这里的代码实现，借助了一个新的数组来保存原数组中移除重复项后的结果。但题目要求是原地删除。因此，需将复制元素到结果数组中改为原地复制。
02代码实现

public int removeDuplicates(int[] nums) {    // 定义变量j，其初始值为0，    // 区间[0,j)表示移除重复元素后，结果数组中的元素    int j = 0;
    // 当前考察的元素    int i = 0;    while (i < nums.length) {        // 查找下一个和当前元素值不相等的元素的下标        int k = nextDifferentNum(i, nums);
        // k-j的值表示当前考察的元素出现的次数        // 而题目要求每个元素最多出现2次        // 因此，需要将k-j的值和2比较，取两者最小值        // 即curNumCount值最大为2        int curNumCount = Math.min(2, k - i);
        // 将当前考察的元素最多只保存2个        for(int n = 0; n < curNumCount; n++) {            // 原地删除            nums[j] = nums[i];            j++;        }
        // 更新i的值为下一个和其值不相等的元素的索引值        // 即下一个要考察的元素        i = k;    }
    return j;}
private int nextDifferentNum(int index, int[] nums) {    for(int m = index; m < nums.length; m++) {        if (nums[m] != nums[index]) {            return m;        }    }    return nums.length;}

更多相关文章

随机推荐