java数组排序从小到大 一道java面试题，20亿数字的文本排序，如何取前100？

一道java面试题，20亿数字的文本排序，如何取前100？

因为这是一个Java问题，所以这是典型的TOPK问题。首先取前100个数字构建一个最小堆，然后依次从堆的顶部插入剩余的数字，同时调整堆。堆中最后100个元素就是结果。空间复杂度为k，时间复杂度为nlogk

所谓的第（第一）k个最大数问题，是指在长度为n（n>=k）的无序数组中，从大到小寻找第（第一）k个数的问题。

解决方案1：我们可以先将无序数组从大到小排序，然后取出最上面的k，总时间复杂度为O（n*logn k）。

解决方案2：使用选择排序或交互式排序，可在选择k次后获得第k个最大数。总时间复杂度为O（n*k）

解决方案3：利用快速排序的思想，从数组s中随机找到一个元素x，将数组分为SA和sb两部分。SA中的元素大于或等于x，sb中的元素小于x。在这种情况下，有两种情况：

1。如果SA中的元素数小于k，则sb中的k-| SA |元素是第k个最大数；

2。如果SA中的元素数大于或等于K，则返回SA中第K个最大的元素数。时间复杂度约为o（n）

解决方案4：二进制[smin，Smax]搜索结果x，统计信息x出现在数组中，整个数组中的k-1数是第k个最大数。平均时间复杂度为O（n*logn）

解决方案5：使用O（4*n）方法为原始数量构建最大堆，然后弹出K次。时间复杂度为O（4*n，K*logn）

解决方案6：保持最小堆大小为K。对于数组中的每个元素，判断堆顶的大小。如果堆顶很大，则无所谓。否则，弹出堆顶并将当前值插入堆中。时间复杂度O（n*logK）

解决方案7：用哈希法保存数组中元素Si的出现次数，利用计数和排序的思想，在由大到小的线性扫描过程中，前面有k-1的数字是第k个最大数，平均时间复杂度O（n）

给定一个乱序数组，找到其中第K大的值，要求？

您创建了一个变量m，并使用它来保存第二大元素，使用max来保存最重要的元素。从max=M=0开始，然后将max与每个元素进行比较。如果元素为>maxmax=element M=max，如果元素小于max，则将M与元素进行比较。如果M<，element M=element，则循环比较正常

java数组排序从小到大 java三个数的排序常用方法 对十个数进行排序java

版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。