【LeetCode】Remove Duplicates from Sorted Array解題レポート

【LeetCode】Remove Duplicates from Sorted Array解題レポート
ラベル(スペース区切り):LeetCode
[LeetCode]
https://leetcode.com/problems/remove-duplicates-from-sorted-array/
Total Accepted: 129010 Total Submissions: 384622 Difficulty: Easy
Question
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example, Given input array nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.
Ways
この問題は見るからに二重ポインタだ.
基本一次AC.
countの初期値は1であることに注意してください.このような意味は、下から直接返すと配列内容が空にならないということです.
最初のコミットは以下の通りで、後で最適化があります.

public class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length<=1)  return nums.length;
        int head=0;
        int next=1;
        int count=1;
        while(next < nums.length){
           while(nums[head] == nums[next]){
               next++;
               if(next>=nums.length)    return count;
           }
           nums[head+1]=nums[next];
           head++;
           next++;
           count++;
        }
        return count;
    }
}

AC:1ms
次はLeetCodeの公式解答です.最初はよくわかりませんでしたが、見てわかりました.待たない限り、頭の針の次の要素を尾の針が指す要素に変えます.等しければ、テールポインタは後ろに進みます.

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int i = 0;
    for (int j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

これを参考にして、私のコードを最適化しました.

public class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length<=1)  return nums.length;
        int head=0;
        int next=1;
        while(next < nums.length){
           if(nums[head] == nums[next]){
               next++;
               continue;
           }
           nums[head+1]=nums[next];
           head++;
           next++;
        }
        return head+1;
    }
}

AC:2ms
遅くなったの?
Date
2016年05月8日