力扣刷题日记/day6/6.28

新手村

删除有序数组中的重复元素，双指针法

此方法有两个要求，要在原数组的基础上进行修改，不动用其它数组

如果数组的长度为0；

直接输出即可

如果数组的长度不为0；

设置两个指针，fast和slow，fast和slow的初值为1，因为要比较fast和fast-1的元素

fast用来遍历所有的数组元素下标，slow用来记录唯一的元素数目

当fast-1和fast指向的元素不相同时，将fast代表的元素给到slow代表的元素，并将++slow，++fast

当fast和fast-1指向的元素相同时，++fast，slow不变

例如下图，当第一次开始循环时，fast-=1，代表的元素0，和fast-1代表的元素相同，此时，fast继续往右前进，slow不变。

 

fast=2时，此时指向的元素为1，和fast-1指向的元素0不同，此时将fast指向的元素1赋给slow指向的元素，nums[slow]=nums[fast],并将slow往右移动，++slow，fast继续往右前进，++fast

 

 

继续前进下去。。。。。。

直到fast=9时（n=10，fast<n），将nums[9]的值赋给nums[4],++slow=5，此时将nums[slow]输出，就是消除了重复元素的数组。

slow就是新的数组的长度，是在原数组的基础上进行修改的。

例题

 解题思路：如上

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n == 0) {    //判断数组的长度是否为0
            return 0;
        }
        int fast = 1, slow = 1;    //设置两个快慢指针
        while (fast < n) {        //数组的长度为n，那么末尾的元素位置是n-1
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;    //最后要输出无重复数组的长度，所以选择++slow
            }
            ++fast;    //防止非法进入循环
        }
        return slow;    //返回无重复数组的长度
    }
}

其余思路：

foreach遍历 (for 每一个)

jdk5.0新特性，新的for循环

for(type x:type Y)

遍历数组或集合Y的元素，每一次遍历把元素值赋给x

例如

for(int num:nums)

就是把nums这个数组进行遍历，它有多少个数，就遍历多少遍。

遍历的时候每次就把其中的一个值给num;

foreach可以使用for语句替代

for(int i =0;i<nums.length;i++){

    System.out.print(nums[i]+" ");

}

通用思路：

 

class Solution {
    public int removeDuplicates(int[] nums) {   
        return process(nums, 1);
    }
    int process(int[] nums, int k) {
        int idx = 0; 
        for (int x : nums) {
            if (idx < k || nums[idx - k] != x) nums[idx++] = x;
        }
        return idx;
    }
}

最后两种思路引用了leetcode上宫水三叶博主的内容，如有侵权，联系删除