-1

我正在实现一个代码以返回数组中的第 n 个最大数，以下是我实现的代码；

public int getNthLargestNum(int [] givenArr, int n){

    int nTotal=0;
    int nNthNum = -1;

    // Remove Duplicates
    Set<Integer> o_hs = new TreeSet<Integer>();
    for(int insert=0; insert<givenArr.length; insert++)
    {o_hs.add(givenArr[insert]);}

    Iterator it  = o_hs.iterator();
    int count=0;

    while(it.hasNext()){
        if(count == n){

        // IF I MOVE THE LINE HERE
        // nNthNum = (Integer)it.next();

            break;
        }
        nNthNum = (Integer)it.next();
        count++; 
    }

return nNthNum;    
}

如果我输入数组 givenArr[4,14,4,5,6,8,9] 和 n=2，则上述程序的输出为 5，但如果我移动行 nNthNum = (Integer)it.next(); 在 if 循环内它输出 4。

所以我很想知道迭代循环我们应该始终实现 it.next()？

4

2 回答 2

1

AHashSet本质上是无序的，因此从集合中获取第 N 项是没有意义的。你不知道你得到了什么价值。该算法本质上是任意的。而是迭代排序的数组以获得第 N 个最大值，或者使用TreeSet非无序的 a。

由于您实际上并不需要排序集中的全部数据，因此您可以随时从集中删除项目。从技术上讲，由于集合最多只有 5 个项目，如果你这样做，每个操作都是 O(1)，使得整个算法 O(n)。

public int getNthLargestNum(int[] data, int n){
    TreeSet<Integer> set = new TreeSet<Integer>();
    foreach(int number : data)
    {
        set.add(number);
        if(set.size() > 5)
            set.pollFirst();
    }

    return set.first();
}
于 2013-07-01T20:37:47.823 回答
0

是的，如果您不这样做it.next()，则不会获取集合中的下一个元素。

it.hasNext()call 不会将指针推进到集合中的下一个元素。

于 2013-07-01T20:35:41.677 回答