如何在数组升序合并方法中实现去重？解决死循环问题

嘿，我来帮你搞定这个头疼的死循环问题！首先咱们得先揪出这类场景下死循环最常见的诱因——数组索引（指针）没有被正确推进，尤其是在处理重复元素的逻辑里，很容易不小心让索引停在原地，导致循环永远跑不完。

先分析可能的错误点 #

你之前的实现大概率是在处理重复元素时，只做了单次的索引移动，或者在某些分支里完全没移动索引。举个例子：如果当两个元素相等时，你只把其中一个数组的索引加1，却忘了处理另一个，或者在跳过重复元素时用了if而不是while，但更致命的是如果某个条件分支里i和j都没变化，那循环就会卡死在这里。

正确的实现思路（双指针+去重） #

因为两个数组都是升序的，咱们可以用双指针法高效处理，同时在每一步都跳过所有重复元素，确保索引持续推进：

• 用两个指针分别指向两个数组的起始位置
• 每次比较指针指向的元素：
  1. 元素相等：将元素加入结果（避免和结果最后一个元素重复），然后同时跳过两个数组中所有和当前元素相同的元素
  2. 元素不等：把较小的元素加入结果，然后跳过对应数组里的所有重复元素
• 当其中一个数组遍历完后，处理另一个数组剩下的元素（同样跳过重复）

具体代码示例（以Java为例，逻辑通用） #

public static int[] mergeAndRemoveDuplicates(int[] arr1, int[] arr2) {
    // 先处理空数组的边界情况
    if (arr1 == null || arr1.length == 0) {
        return removeDuplicatesFromSingleArray(arr2);
    }
    if (arr2 == null || arr2.length == 0) {
        return removeDuplicatesFromSingleArray(arr1);
    }

    int i = 0, j = 0;
    List<Integer> resultList = new ArrayList<>();

    while (i < arr1.length && j < arr2.length) {
        int num1 = arr1[i];
        int num2 = arr2[j];

        if (num1 == num2) {
            // 避免结果里添加重复元素
            if (resultList.isEmpty() || resultList.get(resultList.size() - 1) != num1) {
                resultList.add(num1);
            }
            // 跳过arr1中所有当前重复元素，确保i持续递增
            while (i < arr1.length && arr1[i] == num1) {
                i++;
            }
            // 同样跳过arr2中的重复元素
            while (j < arr2.length && arr2[j] == num2) {
                j++;
            }
        } else if (num1 < num2) {
            if (resultList.isEmpty() || resultList.get(resultList.size() - 1) != num1) {
                resultList.add(num1);
            }
            // 跳过arr1的重复元素
            while (i < arr1.length && arr1[i] == num1) {
                i++;
            }
        } else {
            if (resultList.isEmpty() || resultList.get(resultList.size() - 1) != num2) {
                resultList.add(num2);
            }
            // 跳过arr2的重复元素
            while (j < arr2.length && arr2[j] == num2) {
                j++;
            }
        }
    }

    // 处理arr1剩余的元素
    while (i < arr1.length) {
        int num = arr1[i];
        if (resultList.isEmpty() || resultList.get(resultList.size() - 1) != num) {
            resultList.add(num);
        }
        while (i < arr1.length && arr1[i] == num) {
            i++;
        }
    }

    // 处理arr2剩余的元素
    while (j < arr2.length) {
        int num = arr2[j];
        if (resultList.isEmpty() || resultList.get(resultList.size() - 1) != num) {
            resultList.add(num);
        }
        while (j < arr2.length && arr2[j] == num) {
            j++;
        }
    }

    // 转换为数组返回
    int[] result = new int[resultList.size()];
    for (int k = 0; k < resultList.size(); k++) {
        result[k] = resultList.get(k);
    }
    return result;
}

// 辅助方法：处理单个数组的去重
private static int[] removeDuplicatesFromSingleArray(int[] arr) {
    if (arr == null || arr.length == 0) {
        return new int[0];
    }
    List<Integer> list = new ArrayList<>();
    int prev = arr[0];
    list.add(prev);
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] != prev) {
            list.add(arr[i]);
            prev = arr[i];
        }
    }
    int[] result = new int[list.size()];
    for (int i = 0; i < list.size(); i++) {
        result[i] = list.get(i);
    }
    return result;
}

为什么这个实现不会死循环？ #

每一处处理重复元素的地方都用了while循环，确保索引（i或j）会严格递增，直到超出数组长度或者遇到不同的元素。外层的循环条件i < arr1.length && j < arr2.length也会随着索引的推进最终不满足，循环一定会终止。

自查你的代码 #

你可以对照上面的逻辑检查自己的实现：

• 是不是在某个分支里，i和j都没有被更新？
• 是不是跳过重复元素时用了if而不是while，导致还有重复但不会死循环，但如果是索引没动就会卡死？
• 有没有处理数组为空的边界情况？

内容的提问来源于stack exchange，提问作者Vapor Trails