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

我正在尝试实现该程序以在两个排序数组中找到第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)

有人可以告诉我程序中有什么问题吗？我正在索引超出限制的异常。

最佳答案

我不知道您想做什么，但据我所知，您总是减少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];
}