企业官网建设流程全解析

一.数组中的第K个最大元素

问题概述：

给定整数数组nums和整数k，请返回数组中第k个最大的元素。

请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。

你必须设计并实现时间复杂度为O(n)的算法解决此问题。

思路：

Hoare 分区

就是找排完序，没有去重的第K个最大元素。也就是找索引为n-k的数。

要求O(n)就是排序算法上选优，这里采用类似快排的算法。

快排核心思想：选择一个数作为基数，剩下的数进行划分，比它小的放左边，比它大的放右边。之后递归，在左右区间继续这样操作。代码上实现，使用2个指针，i从左扫到第一个大于它的位置，j从右扫到第一个小于它的位置，然后进行交换。如果i==j那么，i左边都小于哨兵，i右边都大于哨兵，此刻交换哨兵。

【看图写代码-快速排序（交换法+挖空法）】https://www.bilibili.com/video/BV1pd4y1z7gf?vd_source=1d2dfd176f1f132070d67162d5977008

本题难点是边界条件，硬记就行，用do是因为交换后还是需要走一步的，用do方便。

这个当中的意思是，如果k在某一边的区域，只需要对这个区域进行排序，

快速选择

代码：

class Solution { public int findKthLargest(int[] nums, int k) { int n=nums.length; return qsel(nums,0,n-1,n-k); } private int qsel(int[] nums,int l,int r,int k){ if(l==r){ return nums[k]; } int i=l-1,j=r+1; int x=nums[l]; while(i<j){ do i++;while(nums[i]<x); do j--;while(nums[j]>x); if(i<j){ int temp=nums[i]; nums[i]=nums[j]; nums[j]=temp; } } if(k<=j){ return qsel(nums,l,j,k); }else{ return qsel(nums,j+1,r,k); } } }

二.前K个高频元素

问题概述：

给你一个整数数组nums和一个整数k，请你返回其中出现频率前k高的元素。你可以按任意顺序返回答案

思路：

采用最小堆的方法，频率小的放最上面，当元素个数超过k个，就把小头给切掉。最后输出即可。

本代码中是按频率从大到小进行输出的，其实也可以不用这么输出，题目没做要求。

frequencyMap.getOrDefault(num,0): 尝试从frequencyMap中获取键num对应的值

如果num存在：返回其当前频率值

如果num不存在：返回默认值0

.offer()：将元素插入堆中

.poll(): 移除堆顶并返回

.peek(): 查看堆顶不移除

.size(): 查看堆大小 .isEmpty(): 判断堆是否为空

代码：

class Solution { public int[] topKFrequent(int[] nums, int k) { Map<Integer,Integer> frequencyMap=new HashMap<>(); for(int num:nums){ frequencyMap.put(num,frequencyMap.getOrDefault(num,0)+1); } PriorityQueue<Integer> minHeap=new PriorityQueue<>( (a,b)->frequencyMap.get(a)-frequencyMap.get(b) ); for(int num:frequencyMap.keySet()){ minHeap.offer(num); if(minHeap.size()>k){ minHeap.poll(); } } int[] result=new int[k]; for(int i=k-1;i>=0;i--){ result[i]=minHeap.poll(); } return result; } }

三.数据流的中位数

问题概述：

你需要设计一个类MedianFinder，它有两个方法：

1. addNum(int num)：接收一个整数，添加到数据结构中

2. findMedian()：返回当前所有数字的中位数

关键难点：数字是流式添加的，你不知道总共会有多少数字，也不知道数字的顺序，但每次调用findMedian()都要能快速返回当前的中位数。

思路：

不知道总数是奇数还是偶数，采用堆的思想，在加入的过程中进行动态排序，分为俩部分，左部分为大根堆，右部分为小根堆，如果俩堆数量相等就是偶数，取俩堆的顶相加除2.0即可，如果数量不等就是奇数，这里为了方便，让大根堆的数量大一些，如果大根堆数量-小根堆数量>1进行调整，如果小根堆数量小于大根堆数量，也需要调整。始终保持大根堆数量和小根堆的数量差在1以内，并且大根堆最大值小于小根堆最小值。

代码：

class MedianFinder { private PriorityQueue<Integer> minHeap; private PriorityQueue<Integer> maxHeap; public MedianFinder() { maxHeap=new PriorityQueue<Integer>((a,b)->b-a); minHeap=new PriorityQueue<Integer>(); } public void addNum(int num) { if(maxHeap.isEmpty()||num<=maxHeap.peek()){ maxHeap.offer(num); if(maxHeap.size()>minHeap.size()+1){ minHeap.offer(maxHeap.poll()); } }else{ minHeap.offer(num); if(minHeap.size()>maxHeap.size()){ maxHeap.offer(minHeap.poll()); } } } public double findMedian() { if(maxHeap.size()==minHeap.size()){ return (maxHeap.peek()+minHeap.peek())/2.0; }else{ return maxHeap.peek(); } } } /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder obj = new MedianFinder(); * obj.addNum(num); * double param_2 = obj.findMedian(); */