java - 两个排序数组中的第 K 个最小元素 - 错误

Question

我正在尝试实现该程序来查找两个排序数组中的第 k 个最小元素。到目前为止我想出了:

public static int kSmallest(int[] a, int[] b, int aStart, int aEnd,
      int bStart, int bEnd, int k) {
    int lena = aEnd - aStart + 1;
    int lenb = bEnd - bStart + 1;

    if (lena == 0) {
      return b[k - 1];
    }

    if (lenb == 0) {
      return a[k - 1];
    }

    if (k == 1) {
      return Math.min(a[aStart], b[bStart]);
    }

    if(lena + lenb == k){
        return Math.max(a[aEnd], b[bEnd]);
    }

    int i = lena / 2;
    int j = lenb / 2;

    int ma = a[i];
    int mb = b[j];

    if (i + j > k) {
      if (ma < mb) {
        return kSmallest(a, b, i + 1, aEnd, bStart, j - 1, k - i);
      } else {
        return kSmallest(a, b, aStart, i - 1, j + 1, bEnd, k - j);
      }
    } else {
      if (ma < mb) {
        return kSmallest(a, b, i + 1, aEnd, bStart, j - 1, k);
      } else {
        return kSmallest(a, b, aStart, i - 1, j + 1, bEnd, k);
      }
    }

  }

但它给出了错误:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 6
    at arrays.MedianArray.kSmallest(MedianArray.java:90)
    at arrays.MedianArray.kSmallest(MedianArray.java:117)
    at arrays.MedianArray.kSmallest(MedianArray.java:115)
    at arrays.MedianArray.kSmallest(MedianArray.java:115)
    at arrays.MedianArray.main(MedianArray.java:18)

有人可以告诉我我的程序出了什么问题吗？我遇到索引越界异常。

Answer 1

我不明白你想做什么，但据我所知，你总是减少你的 k、lena、lenb。并且 k 的重复使用速度比 lena 和 lenb 更快，因此当 lena 或 lenb 等于 0 时，k 小于 0。因此这些行:

if (lena == 0) {
  return b[k - 1];
}

if (lenb == 0) {
  return a[k - 1];
}

导致 ArrayIndexOutOfBoundsException。

也许你应该尝试这样的事情:

public static int kSmallest(int[] a, int[] b, int aStart, int aEnd,
          int bStart, int bEnd, int k)
{
    int[] aa = new int[aEnd-aStart];
    java.lang.System.arraycopy(a, aStart, aa, 0, aa.length);

    int[] bb = new int[bEnd-bStart];
    java.lang.System.arraycopy(b, bStart, bb, 0, bb.length);

    if(k>aa.length || k>bb.length)
    {
        throw new ArrayIndexOutOfBoundsException();
    }

    return aa[k]<bb[k] ? aa[k] : bb[k];
}