5. 第k大元素

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

审题:输入:目标数n

           输出:数组int[] nums

分析:

        一、关于题目

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

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

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

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

        二、结论

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

         

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 利用快排的思想。 根据基准值(一般为数组的第一个数)。进行左右划分,比基准小的放到基准值右边,反之放左边(因为是第...
    剑戈2阅读 357评论 0 0
  • 描述在数组中找到第k大的元素。给出数组 [9,3,2,4,8],第三大的元素是 4。 Solution使用快排Pa...
    八菜冰阅读 316评论 0 0
  • 题目 描述 在数组中找到第k大的元素 样例 给出数组 [9,3,2,4,8],第三大的元素是 4 给出数组 [1,...
    悠扬前奏阅读 484评论 0 0
  • 描述 在数组中找到第k大的元素 注意事项 你可以交换数组中的元素的位置 样例 给出数组 [9,3,2,4,8],第...
    6默默Welsh阅读 306评论 0 0
  • (对牛弹琴)是心里嫌弃对方听不懂你说的话,不能理解你的意思,觉得白说了。 以前,我们与人交流,沟通时,如果遇上对方...
    谭皓匀阅读 607评论 0 0