LeetCode-初级算法-从排序数组中删除重复项

运行结果

一、题目描述

1、给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

eg :① 给定数组 nums = [1,1,2]，执行代码之后结果为：nums = [ 1 , 2 , 2 ] 方法的返回值为 2
      ② 给定数组 nums = [0,0,1,1,1,2,2,3,3,4] ，执行代码后的结果为：nums = [ 0,1,2,3,4,2,2,3,3,4]，方法的返回值为5

二、分析

1、方法的返回值为原数组中不同数字的个数：n。 如eg②中有0,1,2,3,4总共5个不同的数

2、原数组的前n个数变为这几个不同的数的值，其余的数则不用理会。 如eg②中数组的前5位变为0,1,2,3,4而后面几位的值仍然保持不变。

3、还有一点非常重要，就是给定的数组是已经排序好的。

思路：

1：题目的本质是要从数组中找到不同的数，所以只要找到数组中第 i 个元素，只要这个元素和他后面的一个元素即第 i+1 个元素的值不相等，就说明这个元素是我们想要的。

2：找到这个元素后，就将这个元素赋值给数组的第一个元素，再继续找，再次找到之后将元素赋给第二个元素，一直循环下去。我们可以看到，每次找到我们需要的元素之后要重新赋值给数组中前面的某位置，并且这个位置是要一直往后移的，所以应该做一个计数器，初始值为0，这个计数器作为要赋值给的数组元素的下标，每赋值一个就自增一次，以便于下次赋值。同时这个计数器可以作为方法的返回值，因为数组的长度总是最后一个下标的值+1。

3：经过上面的步骤之后已经完成了一大半，还有一个小bug，那就是我们要判断的是nums [ i ] 与 nums [ i+1 ]的值是否相等，使用for循环时一定要小心数组下标越界的情况，也就是说for循环的条件为i < nums.length - 1;还有一个小bug就是经过for循环后最后一个元素（这里不是指数组的最后一位，而是数组中最后一个不相同的元素）没有办法完成我们想要的操作，因为最后一个重复的元素的后面再也不能找到其它与它取值不同的元素了，但是有一个巧合，那就是数组中的最后一个元素一定是我们需要的那个数（不论最后一个元素重复出现了多少次），因此，在循环结束之后再进行一次操作。就完成了

三、源码

class Solution {
    public int removeDuplicates(int[] nums) {
    	//排除空数组的情况
        if(nums.length == 0){
            return 0;
        }
        
        int count = 0;
        for(int i = 0; i < nums.length-1; i++){
        	//满足if条件的i是我们需要的
             if(nums[i] != nums[i+1]){
                 nums[count++] = nums[i]; 
             }
            }
         //for循环完成之后将数组最后一个元素赋给前面下标为count的元素
         nums[count++] = nums[nums.length-1];
        return count;
    }
}