查找数组实现包中的第 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？

Answer 2

如果你想通过排序来解决问题，那么

1. 使用 API 中的排序方法（Arrays.sort 或 Collections.sort）。重新发明轮子是没有意义的。
2. 对集合的内容进行一次排序，而不是每次查找第 k 个元素时。

快速排序分区适用于查找第 k 个元素，而无需对整个集合进行排序 - 您进行分区，如果最低范围大于 k，则您经常将分区划分到较低范围，如果它小于 k，则转到较高范围并查找（k - 较低范围的大小）第一个元素。它比对整个集合进行排序具有更好的复杂性。您可以在此处阅读更多相关信息。

无论如何，您的方法具有名为 uniqueArr 的参数，但是您可以执行某些操作在rankBagArr 上执行。是拼写错误吗？您的代码中没有rankBagArr 的定义。

Answer 3

希望您可以少一些操作（并提高性能），并更正您所看到的默认值...

从列表（ArrayList）开始，您可以要求对其进行排序（使用比较器和 Collections.List ）。排序（列表））。然后你可以向下循环：

• 如果发现新元素不等于，则记住最后一个元素，
• 增加计数器，当前元素是你的目标
• 当计数器达到 k 值时