JAVA数据结构与算法的学习——判断数组中第K大的元素

╰+攻爆jí腚メ 2022-03-25 12:05 186阅读 0赞

我们来讲讲判**如何判断数组中第K大的元素**这个经典问题，不对之处还请各位不吝赐教。  
看到这个问题，大家应该会觉得很简单，来个**冒泡排序**然后取**第K位**元素不就得了，嗯，对的，的确可以这么做，如果你有看我[上一篇文章][Link 1]的话，你应该会考虑一下如何降低**算法的复杂度**。  
**冒泡排序用法：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwNDMyMw_size_16_color_FFFFFF_t_70]  
**for循环嵌套一个for循环，复杂度就是n的平方**  
**资源图：**  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwNDMyMw_size_16_color_FFFFFF_t_70 1][]  
从资源图可以看出，n的平方随着内容的增加系统资源的利用可直冲冲的升，显然这样的算法太占用资源了，所以我们必须优化一下。  
我们可以用到**java中的最小堆**来实现  
**思维逻辑图：**  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwNDMyMw_size_16_color_FFFFFF_t_70 2][]  
**思维逻辑图要好好看，懂了你就懂整个算法的思路了！  
代码实现：**

import java.util.PriorityQueue;
    
    //实时判断数组中第K大元素
    public class Main2 {
    
    	public static void main(String[] args) {
    		int k=3;
    		int [] arr= {6,7,2,9,0};
    		//PriorityQueue内部数据结构是min-heap
    		PriorityQueue<Integer> p=new PriorityQueue<>(k);
    		for(int i=0;i<arr.length;i++) {
    			if(p.size()<k) {
    				p.offer(arr[i]);//插入元素
    			}else if(p.peek()<arr[i]) {//peek()获取堆顶的值
    				p.poll();//删除堆顶的值
    				p.offer(arr[i]);
    			}
    		}
    		//取堆顶即可
    		System.out.println("第K大的元素是："+p.peek());
    	}
    
    }

这样我们的**复杂度**就降到了**O(5)**，再看看上面的资源图，好好比较两种算法，在比较大的内容下，两种算法占用系统资源相差可不是好几倍呢！

[Link 1]: https://blog.csdn.net/weixin_42404323/article/details/86556885
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwNDMyMw_size_16_color_FFFFFF_t_70]: /images/20220325/9658011df09644f38fc26b84ee706603.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwNDMyMw_size_16_color_FFFFFF_t_70 1]: /images/20220325/41aef267e4dc4c14af0fd79940ea397e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwNDMyMw_size_16_color_FFFFFF_t_70 2]: /images/20220325/0ef9dc38ed74480c8581de2c4987faa5.png