如何合并两个有序数组并仅保留各自独有的元素？

问题回顾 #

需求是合并两个有序数组，生成的结果数组仅包含两个数组中各自独有的元素——即同时出现在两个数组中的元素（包括重复出现的）必须全部排除。示例如下：

输入：
a1 = (1, 2, 3, 4, 4, 4, 5, 5, 6)
a2 = (1, 4, 7, 9)
期望输出：
a3 = (2, 3, 5, 5, 6, 7, 9)

现有代码的问题 #

1. 交集元素移除逻辑错误：第一个双重循环试图通过覆盖a2元素来移除交集，但这种方式会导致数组元素混乱，还可能触发越界（当j为数组最后一个元素时，j+1超出范围），无法彻底清除所有交集元素。
2. 指针递增逻辑错误：后续合并中的连续IF语句会导致指针被错误递增，比如执行a1[i] < a2[j]后i递增，后续判断会使用新的i值，可能触发错误分支。
3. 重复交集元素处理缺失：没有处理数组中重复的交集元素（比如a1中的多个4），仅跳过单个元素会导致残留的交集元素进入结果。

正确思路：双指针遍历法 #

利用数组有序的特性，用双指针同步遍历两个数组，核心逻辑：

• 若a1[i] < a2[j]：a1[i]是a1独有元素，加入结果数组，i自增
• 若a1[i] > a2[j]：a2[j]是a2独有元素，加入结果数组，j自增
• 若a1[i] == a2[j]：该值是交集，跳过a1中所有等于当前值的元素，同时跳过a2中所有等于当前值的元素，避免残留交集元素

修正后的Pascal代码 #

PROGRAM MergeArraysProgram;

PROCEDURE MergeArrays(a1: ARRAY OF INTEGER;
                      n1: INTEGER;
                      a2: ARRAY OF INTEGER;
                      n2: INTEGER;
                      VAR a3: ARRAY OF INTEGER;
                      VAR n3: INTEGER);
VAR
  i, j, currentVal: INTEGER;
BEGIN
  n3 := 0;
  i := 0;
  j := 0;

  WHILE (i < n1) AND (j < n2) DO BEGIN
    IF a1[i] < a2[j] THEN BEGIN
      // a1[i]是独有元素，加入结果
      a3[n3] := a1[i];
      n3 := n3 + 1;
      i := i + 1;
    END
    ELSE IF a1[i] > a2[j] THEN BEGIN
      // a2[j]是独有元素，加入结果
      a3[n3] := a2[j];
      n3 := n3 + 1;
      j := j + 1;
    END
    ELSE BEGIN
      // 找到交集元素，跳过所有相同值
      currentVal := a1[i];
      // 跳过a1中所有等于currentVal的元素
      WHILE (i < n1) AND (a1[i] = currentVal) DO BEGIN
        i := i + 1;
      END;
      // 跳过a2中所有等于currentVal的元素
      WHILE (j < n2) AND (a2[j] = currentVal) DO BEGIN
        j := j + 1;
      END;
    END;
  END;

  // 处理a1中剩余的独有元素
  WHILE (i < n1) DO BEGIN
    a3[n3] := a1[i];
    n3 := n3 + 1;
    i := i + 1;
  END;

  // 处理a2中剩余的独有元素
  WHILE (j < n2) DO BEGIN
    a3[n3] := a2[j];
    n3 := n3 + 1;
    j := j + 1;
  END;
END;

// 测试示例
VAR
  arr1: ARRAY[0..8] OF INTEGER = (1,2,3,4,4,4,5,5,6);
  arr2: ARRAY[0..3] OF INTEGER = (1,4,7,9);
  arr3: ARRAY[0..10] OF INTEGER; // 分配足够大的空间
  len3: INTEGER;
BEGIN
  MergeArrays(arr1, 9, arr2, 4, arr3, len3);
  // 输出结果
  Write('a3 = (');
  FOR i := 0 TO len3-1 DO BEGIN
    Write(arr3[i]);
    IF i < len3-1 THEN Write(', ');
  END;
  WriteLn(')');
END.

代码说明 #

• 使用ELSE IF避免指针被重复递增，确保每次循环只处理一个分支
• 当遇到交集元素时，通过嵌套循环跳过所有相同值，彻底清除交集
• 最后处理两个数组中剩余的元素，确保所有独有元素都被加入结果

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