java - Java中查找两个排序数组的交集

Question

    public class intersect {
  public static void find(int[] a, int[] b, int[] acc) 
  {
    int position = 0;
    for (int j = 0; j < a.length; j++) {
      for (int k = 0; k<b.length; k++) {
        if (a[j] == b[k]) {          
          acc[position] = b[k];
          position++;
        }
      }
    }
    System.out.println(java.util.Arrays.toString(acc));
  }

public static void main (String[] s)
{
  int[] acc = new int[2];
  int[] a = {1,2,3};
  int[] b = {2,3,4};
  find(a, b, acc);
}
}

我写了上面的代码来解决这个问题。但如果你看到的话，功能非常有限，因为我每次都必须更改 acc 的长度。这意味着我必须知道有多少元素相交。在本例中，数组 {1,2,3} 和 {2,3,4} 有共同的 {2,3}，因此 acc 的长度将为 2。

我确信有数百万种方法可以解决这个问题，但我似乎想不出解决这个问题的方法。

请帮忙!

Answer 1

如果你的教授希望你使用数组，你可以使用以下方法:

public static int[] resize(int[] arr)
{
    int len = arr.length;
    int[] copy = new int[len+1];
    for (int i = 0; i < len; i++)
    {
        copy[i] = arr[i];
    }
    return copy;
}

这会将数组的大小增加 1。您可以使用它来代替。顺便说一句，您没有使用它们在 find() 方法中排序的事实。你应该做的是这样的:

public static void find(int[] a, int[] b, int[] acc)
{
    int a_index = 0, b_index = 0, acc_index = -1;
    int a_element, b_element;
    while (a_index < a.length && b_index < b.length)
    {
        a_element = a[a_index]; b_element = b[b_index];
        if (a_element == b_element)
        {
            acc = resize(acc);
            acc[++acc_index] = a_element;
            a_index++; b_index++;
        } else if (b_element < a_element) {
            b_index++;
        } else {
            a_index++;
        }
    }
    System.out.println(java.util.Arrays.toString(acc));
}

现在这个方法效率更高了。 Working example .