5. 第k大元素

2019-01-16  本文已影响0人  NoobA1ex

题目:在数组中找到第k大的元素(JAVA)

审题:输入:目标数n

           输出:数组int[] nums

分析:

        一、关于题目

        1.题目所提供的数组nums是无序的,需要我们排序

        2.通过测试可以发现,题目提供的数组中部分元素会重复出现

        3.题目所提供数组中,元素最大值不超过1,000,000

        4.第k大元素需要的是从大到小的排序,也可以理解为从小到大的倒序

        二、结论

        由于题目的元素最大值不超过1,000,000,在该种情况下时间复杂度为O(n)的桶算法有绝对   优势,可以直接设置一个大小为1,000,000大小的桶用以遍历nums。

         

上一篇下一篇

猜你喜欢

热点阅读