【Java算法】数组合并去重算法-创新互联

• 删除有序数组重复项
• 删除特定值
• 有序数组合并
• 链表去重合并算法

由于数组是有序的，因此只要判断当前数组元素是否与下一个数组元素相等即可，如果相等，那么就继续向后遍历，直到遇到一个不相等的。然后我们可以将这个不相等的，覆盖到第一个重复元素的位置处，这样子就能在不创建一个临时数组的情况下，直接在原数组进行拷贝了。

遇到这种数组去重，删特定值的时候，并且要求不能有新数组，那么一般可以考虑双指针。
也就是定义两个指针，一个slow指针，表示的是不重复元素下一次可以插入的位置，fast用于遍历数组，找出不重复元素。

这里从下标1开始或者从下标0开始都是可以的。

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

既然也是不能创建临时数组，那么就要考虑把特定值给他覆盖掉。
由于要求删除数组中等于 val 的元素，因此输出数组的长度一定小于等于输入数组的长度，我们可以把输出的数组直接写在输入数组上。可以使用双指针：右指针fast指向当前将要处理的元素，左指针slow指向下一个将要赋值的位置。

如果右指针指向的元素不等于 val，它一定是输出数组的一个元素，我们就将右指针指向的元素复制到左指针位置，然后将左右指针同时右移；

如果右指针指向的元素等于 val，它不能在输出数组里，此时左指针不动，右指针右移一位。
也就是，如果遍历的指针（右指针）遇到的值等于val，那么直接忽略，但是如果遇到的值不是，那么就把这个值覆盖到左指针指向的位置。

public int removeElement(int[] nums, int val) {
        int slow = 0;//双指针 slow代表的是非val值可以插入的下一个位置
        int fast = 0;//fast用于遍历
        int n=nums.length;
        while (fast

//    public static void merge(int[] nums1, int m, int[] nums2, int n) {
//        for (int i=m,j=0;i= 0 || p2 >= 0) {
            if (p1 == -1) {
                cur = nums2[p2--];
            } else if (p2 == -1) {
                cur = nums1[p1--];
            } else if (nums1[p1] >nums2[p2]) {
                cur = nums1[p1--];
            } else {
                cur = nums2[p2--];
            }
            nums1[tail--] = cur;
        }
    }