有序数组差集实现问题：如何编写通用的h1-h2差集求解方法

Hey there! Let's get that sorted array difference method working for all cases. Your current code only handles scenarios where every element in h1 is smaller than those in h2, but we can fix this with a two-pointer technique—perfect for sorted arrays since it’s efficient (O(n+m) time, O(1) extra space if we don’t count the output) and covers all edge cases.

Why Your Original Code Fails #

From what you described, your existing logic probably assumes h1’s elements are all smaller than h2’s, so it just prints everything in h1 without checking for overlapping values in the middle or end of the arrays. For example, if h1 = [1,3,5] and h2 = [2,3], your code would miss checking if 3 exists in h2, leading to incorrect output.

Solution: Two-Pointer Approach #

Since both arrays are sorted, we can use two pointers to traverse h1 and h2 in parallel, comparing elements to decide what to print:

• Initialize pointers i (for h1) and j (for h2) at index 0.
• Loop while both pointers are within their array bounds:
  • If h1[i] < h2[j]: This element in h1 can’t exist in h2 (since h2 is sorted), so print it and move i forward.
  • If h1[i] == h2[j]: This element exists in both arrays, so skip all occurrences of this value in both arrays (to handle duplicates) and move both pointers past them.
  • If h1[i] > h2[j]: The current element in h2 is too small, move j forward to find a possible match for h1[i].
• After the loop, print any remaining elements in h1 (they’re all larger than everything in h2, so they can’t be in h2).

Working Code Example #

private void printDifference(int[] h1, int[] h2) {
    int i = 0, j = 0;
    int len1 = h1.length;
    int len2 = h2.length;

    while (i < len1 && j < len2) {
        if (h1[i] < h2[j]) {
            System.out.println(h1[i]);
            i++;
        } else if (h1[i] > h2[j]) {
            j++;
        } else {
            // Skip all occurrences of the common value in both arrays
            int commonVal = h1[i];
            while (i < len1 && h1[i] == commonVal) {
                i++;
            }
            while (j < len2 && h2[j] == commonVal) {
                j++;
            }
        }
    }

    // Print any remaining elements in h1
    while (i < len1) {
        System.out.println(h1[i]);
        i++;
    }
}

Alternative: Using a HashSet (Simpler for Small Arrays) #

If you don’t mind using extra space, a HashSet approach is straightforward and works regardless of array order (though since your arrays are sorted, the two-pointer method is more efficient):

private void printDifferenceUsingSet(int[] h1, int[] h2) {
    Set<Integer> h2Elements = new HashSet<>();
    for (int num : h2) {
        h2Elements.add(num);
    }
    for (int num : h1) {
        if (!h2Elements.contains(num)) {
            System.out.println(num);
        }
    }
}

Key Edge Cases Handled #

• h1 has elements interspersed with h2 (e.g., h1 = [2,4,6], h2 = [3,4])
• Duplicate elements in either array (e.g., h1 = [1,1,3], h2 = [1])
• h1 is shorter than h2 (e.g., h1 = [1,2], h2 = [1,3,4])
• h2 is shorter than h1 (e.g., h1 = [1,3,5], h2 = [2])

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