0

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

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;
}
4

3 回答 3

3

首先，这部分是高度怀疑的：

  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吗？

于 2009-09-09T08:44:27.083 回答
1

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

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

快速排序分区适用于在不对整个集合进行排序的情况下查找第 k 个元素 - 您进行分区，如果最低范围大于 k，则您经常将分区转到较低范围，如果它小于 k，则转到较高范围并寻找(k - 下限的大小)-th 元素。它比对整个集合进行排序具有更好的复杂性。你可以在这里阅读更多关于它的信息

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

于 2009-09-09T10:43:55.907 回答
0

愿您可以少一些操作（并提高性能），并更正您看到的默认设置...

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

  • 记住最后一个元素
  • 如果你发现新元素不等于，增加一个计数器
  • 当您的计数器达到 k 值时，当前元素就是您的目标
于 2009-09-09T08:46:36.220 回答