问：假如一个整数列表（允许重复）;和整数N.从列表中删除重复项，并找到在修改后的列表中的N个最大的元素。实现至少两个不同的解决方案，以查找与O（N *日志（N））在大O符号平均时间复杂度，其中N是在该列表中的元素的数量N个最大的元素

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.

据我的了解，我可以使用归并排序，堆排序，快速排序所提供的整数列表重复上找到与大O O（N *日志（N））的平均时间复杂度的N个最大的元素符号。那是对的吗 ？

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 ?

另外，怎么样在列表中重复做我只是添加在上述算法的code一个额外的行删除重复的将是不影响O（N *日志（N））的平均时间复杂度，因为合并排序，堆排序，快速排序将只对列表进行排序不删除重复。

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.

我不想找任何code，但只是技巧和想法有关如何处理这个问题？我使用Java也有pdefined归类/方法，在java中，我可以用它来完成任务，而不是我的编码归并排序，堆排序，对我自己的快速排序任何$ P $。

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.

我的目标是完成任务牢记O（N *日志（N））的平均时间复杂度。

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

推荐答案

既然你加入Java作为一个标签：

Since you added java as a tag:

List<Integer> listWithoutDuplicates = new ArrayList(new TreeSet(originalList));

这将建立一个新的，排序的列表没有重复。关于时间复杂度，这加起来为O（n * log n）的（在建设有n个元素的二进制平衡树的复杂性）。作为奖励，你可以尝试和LinkedHashSet替换TreeSet中以preserve元素的顺序（重复之中，我认为最后一个保管）。

This will construct a new, sorted list without duplicates. Regarding time complexity, this adds up to O(n*log n) (the complexity of constructing a binary balanced tree with n elements). As a bonus, you can try and replace TreeSet with LinkedHashSet to preserve elements' order (among duplicates, I think the last one is kept).

关于最后部分，通过索引中删除一个元素是直线前进之后。

About the last part, removing an element by index is straight forward afterwards.

当然，如果是一个家庭作业的问题，您可能需要实现自己的红黑树来得到同样的结果。

Of course, if it is a homework question, you may need to implement your own red-black tree to get the same result.