发现排列第k个最大的元素袋

我们收集了一个Comparable s在一个袋子里，必须找到第k第一大元素。我将集合复制到HashSet以删除重复项，然后将HashSet转换为要排序的数组，然后访问第k个元素。代码编译，但测试失败，我无法弄清楚什么是错的。有任何想法吗？发现排列第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; 
}

来源

2009-09-09 learner01

什么是rankBagArr？这是一个错字，应该是唯一的吗？ – 2009-09-09 08:47:59

一开始这部分是高度怀疑：

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-09 08:44:27

也许你可以有少了几分操作的（并提高性能），并纠正您所看到的默认...

用List（ArrayList的）开始，你可以要求对它进行排序（使用比较器和Collections.sort(list)）。然后，您可以循环下来：

记忆的最后一个元素
如果你找到新的元素不等于，递增计数器
当您的计数器达到k值，当前元素是你的目标

来源

2009-09-09 08:46:36 KLE

如果你想通过排序，然后

使用排序从API方法（Arrays.sort解决问题或Collections.sort）。重新发明轮子毫无意义。
对你的收藏的内容进行一次排序，而不是每次查找第k个元素。

快速排序分区适用于在不排序整个集合的情况下查找第k个元素 - 如果最小范围大于k，那么您经常使用分区降低范围，如果它小于k，到更高的范围并寻找（k范围下限）第 - 个元素。它比分类整个集合要复杂得多。您可以阅读更多关于它的信息here

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

来源

2009-09-09 10:43:55

发现排列第k个最大的元素袋

回答

相关问题