So I'm doing the leetcode question "Top K Frequent Element" and I used priorityQueue for frequency. When I start to poll the numbers and insert into arraylist, somehow the for loop doesn't poll out all the elements in the Queue. Why?
(Say PQ has two elements)
while(!pq.isEmpty()){
ls.add(pq.poll());
}
for(int b = 0; b < pq.size();b++){
ls.add(pq.poll());
}
Shouldn't these two loops print out the same thing?
I got the correct answer from the while loop while I only got one element from the for loop
The difference with the second approach is that the value of b < pq.size() is changing at each iteration, as the number of element decreases when you remove an element: pq.poll(). To obtain the same result (assuming that we don't add further elements to the queue while doing the iteration), try this:
for (int b = 0, n = pq.size(); b < n; b++) {
ls.add(pq.poll());
}
In the above snippet, we save the size of pq exactly once at the start of the iteration, to make sure it doesn't change. This will work even better, because it accounts for the case of concurrent insertions/deletions:
while (pq.size() > 0) {
ls.add(pq.poll());
}