26. Remove Duplicates from Sorted Array

青旅半醒 2022-08-20 13:21 42阅读 0赞

Problem:

> 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.

Analysis：

> 首先读清题意，题目很简单，删除数组（sorted）中重复的元素，然后返回唯一元素的大小。A数组要变化。
> 
> 分两种情况：
> 
> 1》若数族大小为0/1。 数组A 不变，返回0/1。
> 
> 2》 若数组大小大于1。用count记录新数组元素A的末尾的下一个index，若a\[i\] != a\[i-1\], 则把  
> a\[i\]的值赋给count位置上（a\[count\] = a\[i\] )。
> 
> 例如数组元素为 1, 2 2, 2 2, 3, 3, 4。 此时count=2,表示A的下标2前面有两个不同的元素，若  
> A\[5\]=3,A\[4\]=2, 则到A\[5\] != A\[4\]时，将A\[5\]的只赋给A\[count\]上，然后count++。

Anwser1：

1.  这个方法显得很笨拙，很直白，利用前后两个元素比较，如果相同则后面的元素替代这个相同的元素，然后进行下一个比较，这个方法之所以笨拙是因为结果要求只算出不同元素的个数，没有要求数组改变，而本方法对数组进行了移位操作，浪费了时间。
2.  这个题考查的是双指针的概念，应该利用双指针实现。

//笨方法
    public class Solution {
        public int removeDuplicates(int[] nums) {
            if(nums.length==0) return 0;
            if(nums.length==1) return 1;
            int i=1;
            int temp=nums[0];
            int length=nums.length;
            while(i<length){
                if(temp!=nums[i]) {
                    temp=nums[i];
                    i++;
                }
                else{
                    for(int j=i;j<=length-1;j++){
                        nums[j-1]=nums[j];
                    }
                    length--;
                }
            }
            return length;
        }
    }

Anwser2:

//双指针
    public class Solution {
        
        public int removeDuplicates(int[] nums) {
            if(nums.length==0) return 0;
            if(nums.length==1) return 1;
            int count=1;
            for(int i=1;i<nums.length;i++){
                if(nums[count-1]!=nums[i]) {
                //if 条件改为(nums[i-1]!=nums[i])也可以
                    nums[count]=nums[i];
                    count++;
                }
            }
            return count;
        }
    }

下面代码是方法2的不同写法，即用了2个指针：

public static int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        if (nums.length == 1)
            return 1;
        int slow = 0, fast = 1, len = nums.length;
        while (fast < len) {
            if (nums[fast] != nums[slow]) {
                nums[++slow] = nums[fast];
            }
            fast++;
        }
        return slow + 1;
    }