有序数组重复元素查找算法实现的正确性与效率咨询

提交代码 #

private static int findDuplicatesFinalVersion(int[] arr1, int[] arr2) {
    int count = 0;
    int index1 = 0;
    int index2 = 0;

    while (index1 < arr1.length && index2 < arr2.length) {
        if (arr1[index1] < arr2[index2]) {
            index1++;
        } else if (arr1[index1] == arr2[index2]) {
            count++;
            index1++;
            index2++;
        } else {
            index2++;
        }
    }
    return count;
}

作业要求 #

跟踪第一个数组的下一个元素。若第二个数组的下一个元素小于第一个数组的下一个元素，则移动第二个数组的指针；若相等（即找到重复元素）或更大，则移动第一个数组的指针。假设两个数组自身无重复元素（使用前例中的生成器）。运行基准测试，对比该实现与无序数组查找、二分查找的执行时间。

代码审查 #

1. 与作业要求匹配度 #

你的代码逻辑完全符合作业要求：

• 当arr2[index2] < arr1[index1]（对应代码arr1[index1] > arr2[index2]分支）时，移动第二个数组指针index2
• 当arr2[index2] >= arr1[index1]时：
  • 若元素相等，计数后同时移动两个指针（因数组自身无重复，该操作比仅移动第一个指针更高效，避免重复匹配同一元素）
  • 若arr2[index2] > arr1[index1]（对应代码arr1[index1] < arr2[index2]分支），移动第一个数组指针index1

2. 正确性 #

代码逻辑完全正确：

• 依托两个有序数组的递增特性，双指针遍历不会遗漏任何重复元素
• 数组自身无重复的前提下，相等时同时移动指针的操作，不会导致重复计数或漏数
• 循环终止条件index1 < arr1.length && index2 < arr2.length确保不会出现数组越界问题

3. 效率 #

该实现的时间复杂度为O(m + n)（m、n为两个数组的长度），是有序数组交集查找的最优时间复杂度之一：

• 无需额外空间（仅使用几个变量），空间复杂度为O(1)
• 对比二分查找方案（时间复杂度O(m log n)或O(n log m)），当两个数组长度接近时，双指针的性能优势明显；仅当其中一个数组长度远小于另一个时，二分查找的效率才会反超

改进建议 #

• 添加参数校验：在方法开头增加对arr1、arr2是否为null的判断，避免空指针异常，示例代码：

  if (arr1 == null || arr2 == null) {
      return 0;
  }
  

• 针对极端长度差优化：如果两个数组长度差异极大（比如一个长度100，另一个100000），可以改为对短数组的每个元素在长数组中执行二分查找，时间复杂度变为O(min(m,n) * log max(m,n))，此时性能会优于双指针
• 扩展功能（可选）：如果需要返回具体的重复元素而非仅计数，可以在找到相等元素时将其存入List，最后返回List或同时返回计数与列表
• 变量名简化（可选）：可以将index1、index2改为i、j或ptr1、ptr2，进一步提升代码可读性

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