java - 查找数组实现包中的第 k 个最大元素

Question

我们有一个装在袋子里的Comparable集合，并且必须找到第k最大的元素。我将集合复制到 HashSet 以删除重复项，然后将 HashSet 转换为要排序的数组，从而访问第 k 个元素。代码可以编译，但测试失败，我不知道出了什么问题。有什么想法吗？

public E kth(int k) {
    uniqueSet();
    Object[] uniqueArr = hashSet.toArray();
    startQuick(uniqueArr);
    return (E) uniqueArr[k - 1];
}

private void startQuick(Object[] uniqueArr) {
  int i = 0, j = uniqueArr.length;
  quickSort(uniqueArr, 0, j);
}

private void quickSort(Object[] uniqueArr, int i, int j) {
    int index = partition(uniqueArr, i, j);
    if (i < index - 1) {
        quickSort(rankBagArr, index - 1, j);
    }
    if (index < j) {
        quickSort(rankBagArr, i, index - 1);
    }
}

private int partition(Object[] uniqueArr, int i, int j) {
    E tmp;
    E pivot = (E) rankBagArr[(i + j) / 2];

    while (i <= j) {
        while (rankBagArr[i].compareTo(pivot) < 0) {
            i++;
        }
        while (rankBagArr[j].compareTo(pivot) > 0) {
            j--;
        }

        if (i <= j) {
            tmp = (E) rankBagArr[i];
            rankBagArr[i] = rankBagArr[j];
            rankBagArr[j] = tmp;
            i++;
            j--;
        }
    }
    return i;
}

Answer 1

首先，这部分非常可疑:

  if (i < index - 1)
        quickSort(rankBagArr, index-1 ,j);
  if (index < j)
        quickSort(rankBagArr, i, index-1);

你的意思是不是:

  if (i < index - 1)
        quickSort(rankBagArr, i, index-1);
  if (index + 1 < j)
        quickSort(rankBagArr, index + 1, j);

？

我不熟悉你的分区方法，所以我不知道这是否正确。我认为我理解它，并且检查起来看起来还不错，但是很容易出现一点点错误，如果不仔细研究，很难发现这些错误。

这是我最近用 C# 编写的一个分区方法 - 如果您愿意，您应该能够很容易地将其转换为 Java。

private static int Partition<T>(T[] array, int left, int right,
  IComparer<T> comparer) {
  // Pivot on the rightmost element to avoid an extra swap
  T pivotValue = array[right];
  int storeIndex = left;
  for (int i = left; i < right; i++) {
    if (comparer.Compare(array[i], pivotValue) < 0) {
      Swap(array, i, storeIndex);
      storeIndex++;
    }
  }
  Swap(array, right, storeIndex);
  return storeIndex;
}

static void Swap<T>(T[] array, int x, int y) {
  T tmp = array[x];
  array[x] = array[y];
  array[y] = tmp;
}

不只使用 Arrays.sort 的任何原因不过？