algorithm - Java/Jsp programming quiz with respect to Big-O notation

Question

Question: Given: a list of integers (duplicates are allowed); and integer N. Remove the duplicates from the list and find the N-th largest element in the modified list. Implement at least two different solutions to find N-th largest element with O(N*log(N)) average time complexity in Big-O notation, where N is the number of elements in the list.

According to my understanding i can use Merge Sort, Heap Sort, Quick sort on the provided integer list with duplicates to find the N-th largest element with O(N*log(N)) average time complexity in Big-O notation. Is that correct ?

Also, what about duplicates in the list do i just add an extra line of code in the above mentioned algorithm to remove duplicates will that not affect the O(N*log(N)) average time complexity because Merge Sort, Heap Sort, Quick sort will only sort the list not delete duplicates.

I am not looking for any code but just tips and ideas about how to proceed with the question ? I am using Java also is there any predefined classed/methods in java that i can use to accomplish the task rather than me coding Merge Sort, Heap Sort, Quick sort on my own.

My aim is to complete the task keeping in mind O(N*log(N)) average time complexity.

Answer 1

You first sort the list and then you remove illiterate over it to find all the duplicates. A second methode might be to loop over all elements and keep a tree structure in which for each element you first check if it's already present in the tree structure O(log(n)) and if is remove it else add it to the tree structure O(log(n)). This makes the whole algorithm O(n(log(n))).