力扣215.数组中的第K个最大元素-堆排序法java
目录
力扣215.数组中的第K个最大元素–堆排序法(java)
为了找到数组中第K个最大的元素，我们可以使用堆排序的方法。堆排序的核心是构建一个最大堆，并通过多次交换堆顶元素来找到前K个最大的元素。具体步骤如下：
方法思路
构建最大堆：将输入数组转换为最大堆，使得每个父节点的值大于其子节点的值。
交换并调整堆：执行K次交换操作，每次将堆顶元素（当前最大值）与当前堆的末尾元素交换，然后调整剩下的元素以维持最大堆的性质。
获取结果：经过K次交换后，第K个最大的元素会位于数组的倒数第K个位置。
解决代码
class Solution {
class Heap{
int size;
int[] nums;
public Heap(int[] nums){
this.nums = nums;
this.size = nums.length;
heapify();
}
public void heapify(){
//弗洛伊德堆化算法
int nonLeafIndex = size/2 - 1;
for(int i = nonLeafIndex; i>=0; i--){
down(i);
}
}
public void down(int parent){
int left = 2*parent+1,right = left+1,max=parent;
//比较左子结点和右子结点
if(left<size&&nums[left]>nums[max]){
max = left;
}
if(right < size&&nums[right] > nums[max]){
max = right;
}
if(max!=parent){
swap(nums,max,parent);
down(max);
}
}
public int poll(){
int polled = nums[0];
swap(nums, 0, size-1);
size--;
down(0); //调整堆结构
return polled;
}
public void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
public int findKthLargest(int[] nums, int k) {
Heap heap = new Heap(nums);
//k=2
while(k-- > 1){
heap.poll();
}
return heap.poll();
}
}该方法的时间复杂度为O(n + k log n)，其中构建堆的时间为O(n)，每次调整堆的时间为O(log n)，共进行k次调整。空间复杂度为O(1)，因为所有操作都在原数组上进行。