剑指offer—数组前K个元素 TopK 解答

剑指offer—数组前K个元素 TopK

Java中优先队列的实现就是堆排序

题目描述

输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。

思路

考虑到最快的排序时间为O(NlogN),并且时间复杂度为O(1)的堆排序

  • 堆是由完全二叉树构成,一定是连续的,所以可以写成数组的形式。

大根堆:每一个节点的左右孩子都小于根节点

小根堆:每一个节点的左右孩子都大于根节点

堆排序过程:

  • 构建堆:(让初始序列数组堆化,满足堆的条件)
  • 调整堆:构建成堆后,此时堆还无序,我们需要调整,循环n次,每次堆化前把根节点和最后一个叶子节点交换,并且移除交换到叶子节点的根,然后开始堆化,n次循环后,堆就是有序的。

代码

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if(input.length==0||k>input.length) return list;
        //构建最大堆
        for(int m=(input.length/2-1);m>=0;m--){//从最后一个叶子节点的父亲节点开始,每次往前移动
            heapify(input,input.length,m);//对m节点堆化
        }
        //调整堆
        for(int i=input.length-1;i>=1;i--){
            swap(input,0,i);//交换叶子节点和根节点
            heapify(input,i,0);//对根节点堆化
        }
        for(int n=0;n<k;n++){//添加前k个元素
            list.add(input[n]);
        }
        return list;
    }

   public void heapify(int[] a,int l,int current){//传入数组,数组长度(用于判断),当前元素位置下标
        int left = current*2+1;//左孩子数组下标
        while(current>=0&&left<l){
            if((left+1)<l&&a[left]<a[left+1]){//比较左孩子和右孩子,保存较大的孩子到left
                left++;
            }
            if(left<l&&a[left]>a[current]){//如果较大的孩子大于当前节点值,交换并且更新位置,继续循环,否则退出迭代
                swap(a,left,current);
                current = left;
                left = current*2+1;
                continue;
            }
            break;
        }
    }
    public void swap(int[] array,int a,int b){
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

拓展—LeetCode215—数组第k个最大元素

题目描述

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

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:

你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。

思路

与上面一题一样,只不过不需要保存到集合,直接输出第length-k个元素

代码

import java.util.Arrays;

class Solution {
    //堆排序
    public int findKthLargest(int[] input, int k) {
        if(input.length==0||k>input.length) return 0;
        //构建最大堆
        for(int m=(input.length/2-1);m>=0;m--){
            heapify(input,input.length,m);
        }
        //调整堆
        for(int i=input.length-1;i>=1;i--){
            swap(input,0,i);
            heapify(input,i,0);
        }
         return input[input.length-k];
    }

    public void heapify(int[] a,int l,int current){
        int left = current*2+1;
        while(current>=0&&left<l){
            if((left+1)<l&&a[left]<a[left+1]){
                left++;
            }
            if(left<l&&a[left]>a[current]){
                swap(a,left,current);
                current = left;
                left = current*2+1;
                continue;
            }
            break;
        }
    }

    public void swap(int[] array,int a,int b){
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/topk.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!