Leetcode26-源址法-低复杂度数组去重

leetcode 26 , 标题党一波，所谓“源址法”，自己理解是不改变数据存储的地址或内存区域，包括移动，新建，复制等方式。"低复杂度"则包括时间和空间的复杂度两方面，本例中，主要是题目要求不能新建数组，做了空间上的限制。但是题目描述有些模棱两可。我们知道数组一旦申请其空间是固定的（此处仅指基本类型的array），所以当要求去重时，首先想到再复制，已经不行。其次想到删除，所以会在这里造成疑惑。
其实题目中说明了目标方法返回值是新的数组的长度，且入参数组是有续的，所以最终判定是通过这两个因素来检查结果的，所以还是要注意审题。

Wiki 有关于“源址法” in-place 的相关介绍，道理很简单，应用很复杂

题目要求：
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 by modifying the input array in-place with O(1) extra memory.
Example:
Given 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.(这句比较关键)

代码和解答
使用两个序号记录所在index，前序 i = 0,后继 j = 1,只需要遍历一遍就可以完成，在发现非等值的时候，放到 i++的位置，如果相等则 j 往后继续。
通过图例能清楚解释。

示例图

/**
 * Created by igoso on 18-1-30.
 * array [1,1,2] -> [1,2]
 * 题目描述有点模棱两可,要求不引入新数组,复杂度在O(1)。重要的是清楚 1.返回值是新数组的长度 2.数组是有序的 3.结果数组是入参，但长度做了更新，关联 1。
 */
public class Leet26 {
    public static void main(String[] args) {
        int[] nums1 = new int[]{1, 1, 2};
        removeDuplicates(nums1);
    }

    public static 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;
    }
}