Working of Iterator in Java

Question

I was implementing a code to return the nth Largest Number in an array, Following is the code I implemented;

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

If I input the array givenArr[4,14,4,5,6,8,9] and n=2 the output is 5 for the above program but if I move the line nNthNum = (Integer)it.next(); inside the if loop it outputs 4.

So I was curious to know to iterate through the loop we should always implement it.next()?

Servy · Accepted Answer · 2013-07-01T21:09:12.730

1

A HashSet is inherently unordered, so getting the N-th item from the set is meaningless. You have no idea what value you get. The algorithm is inherently arbitrary. Instead iterate the sorted array to get the N-th largest value, or use a TreeSet which is not unordered.

Since you don't actually need the entire data in the sorted set you can remove items from the set as you go. Technically, since the set only ever has a maximum of 5 items if you do that each operation is O(1), making the whole algorithm 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();
}

edited Jul 01 '13 at 21:09

answered Jul 01 '13 at 20:37

Servy

202,030
26
332
449

I was planning to use Set to reomove the duplicates. But TreeSet would take a perfomrance hit if the data is huge right? Is there any other way to remove duplicates. I understand I can use HashMaps and store the count as value, is there any other alternative than HashMap too? – JNL Jul 01 '13 at 20:47
`TreeSet` wouldn't incur any greater performance hit than you'd already get from `Arrays.sort`. – Louis Wasserman Jul 01 '13 at 20:51
@JNL Calling `Sort` on your data will already have an equal performance impact to using a `SortedSet`. Adding n items to a `SortedSet` is O(n*log(n)), sorting n items is O(n*log(n)). By adding the items to a `SortedSet` you won't *need* to do the array sort. Also, focus on getting working data first, then optimize as needed. There's no sense using an algorithm that's way faster when it produces the wrong result. – Servy Jul 01 '13 at 20:51
@Servy Thanks for the same Servy. I tried to break the earlier implementation with HashSet and including negative numbers and it did not work as intented. I edidted it to use TreeSet. I was wonderring if we can we do in O(n) time? – JNL Jul 01 '13 at 20:56
@JNL Yous should include that in the question then, it's simple enough to do. – Servy Jul 01 '13 at 21:09
@Servy http://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on This is the link for the same. Thanks – JNL Jul 01 '13 at 21:14

score 0 · Answer 2 · answered Jul 01 '13 at 20:35

0

Yes, if you don't do it.next(), next element in collection will not be fetched.

it.hasNext() call will not advance pointer to next element in collection.

answered Jul 01 '13 at 20:35

kosa

65,990
13
130
167

Working of Iterator in Java

2 Answers2