力扣刷題日記/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上宮水三葉博主的內容，如有侵權，聯系删除