【算法】数组合并去重算法

Myth丶恋晨 2024-03-29 15:45 72阅读 0赞

#### 文章目录 ####

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

## 删除有序数组重复项 ##

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

遇到这种数组去重，删特定值的时候，并且要求不能有新数组，那么一般可以考虑双指针。  
也就是定义两个指针，一个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<n){
                if (nums[fast]!=val){
                    nums[slow++]=nums[fast];
                }
                fast++;
            }
            return slow;
        }

## 有序数组合并 ##

已知两个有序数组，其中第一个有序数组的元素个数为m，第二个有序数组的个数为n。  
因此为了能在第一个数组上直接对两个数组进行合并，那么第一个数组的大小应该设定为m+n，也就是合并之后的总大小。  
之后，就可以开始考虑如何把两个数组进行合并了。其中第一个数组的尾部的数据均为0，长度为n。  
大致如下  
输入：nums1 = \[1,2,3,0,0,0\], m = 3, nums2 = \[2,5,6\], n = 3  
输出：\[1,2,2,3,5,6\]  
解释：需要合并 \[1,2,3\] 和 \[2,5,6\] 。  
合并结果是 \[1,2,2,3,5,6\] ，其中斜体加粗标注的为 nums1 中的元素。  
考虑到当前数组1的尾部有空余元素，因此可以考虑尾插法，从两个数组的有效数据的尾部开始遍历，把更大的数据放在数组的尾部，这样子就能节省一个临时数组了。

//    public static void merge(int[] nums1, int m, int[] nums2, int n) {
    //        for (int i=m,j=0;i<nums1.length;i++){
    //            nums1[i]=nums2[j++];
    //        }
    //        Arrays.sort(nums1);
    //    }
    
        public static void merge(int[] nums1, int m, int[] nums2, int n) {
            int p1 = m - 1, p2 = n - 1;
            int tail = m + n - 1;
            int cur;
            while (p1 >= 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;
            }
        }

## [链表去重合并算法][Link 1] ##

[Link 1]: https://blog.csdn.net/Zhangsama1/article/details/128744344?spm=1001.2014.3001.5502