剑指offer第六天

29.最小的K个数

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

解法一:

Partition思想

允许改变原始数组的情况,时间复杂度O(n),不适合海量数据

import java.util.ArrayList;
public class Solution {
    /*解法一:允许改变原始数组的情况,时间复杂度O(n),不适合海量数据*/
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> result = new ArrayList<>();
        //注意如果输入不合法,这里返回的是一个空集合,不是Null,与return null不同
        if(input == null || k<0 || k>input.length) return result;
        
        int start = 0;
        int end = input.length-1;
        int smallNums = partition(input,start,end);
        while(smallNums != k-1){
            if(smallNums > k-1)
                smallNums = partition(input,start,smallNums-1);
            else if(smallNums < k-1)
                smallNums = partition(input,smallNums+1,end);
        }
        for(int i =0;i<k;i++){
            result.add(input[i]);
        }
        return result;
    }
    //快排方法功能函数,在指定范围内随机选取一个数字,将数组中大与等于的放置其又,小于的放置其左;
    //返回值是在变换位置后,该元素的索引值
    public static int partition(int[] array,int start,int end){
        //边界检测
        if(array == null || array.length == 0 || start < 0 || end >= array.length || start > end) return -1;
        //在[start,end]范围内,随机选取一个数作为index
        int randomIdx = (int)(start + Math.random()*(end-start));
        //int length = array.length;
        int smallNums = start-1;
        swap(array,randomIdx,end);
        for(int i=start;i<end;i++){
            if(array[i] < array[end]){
                smallNums++;
                if(smallNums < i){
                    swap(array,smallNums,i);
                }
            }
        }
        
        smallNums++;
        swap(array,smallNums,end);
        return smallNums;
    }
    //交换元素
    public static void swap(int[] array,int i,int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

解法二:

使用最大堆思想,通过优先队列的Conparator定制排序,实现指定大小的最大堆。

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Solution {
    //解法二:不改变原始数组,使用优先队列,时间复杂度O(nlogk),适合海量数据
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> result = new ArrayList<>();
        if(input == null || k > input.length || k<=0) return result;
        PriorityQueue<Integer> maxQueue = new PriorityQueue(k,new Comparator<Integer>(){
            @Override
            public int compare(Integer o1,Integer o2){
                return o2.compareTo(o1);//将先前Integer中的自然排序(从小到大)反过来,实现从大到小;
            }
        });
        for(int i =0;i<input.length;i++){
            if(maxQueue.size() != k ){
                maxQueue.offer(input[i]);
            }else if(maxQueue.peek() > input[i]){
                Integer temp = maxQueue.poll();//必须先去除队列头部的数据,以保证队列长度
                temp = null;
                maxQueue.offer(input[i]);
            }
        }
        for(Integer i : maxQueue){
            result.add(i);
        }
        return result;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏haifeiWu与他朋友们的专栏

聊聊HashSet源码

今天聊一下HashSet源码,HashSet内部基本使用HashMap来实现,本博客将通过一下几个方向讲解。

9730
来自专栏LeetCode

leetCode 77&39. Combinations & Combination Sum

Given two integers n and k, return all possible combinations of k numbers out of...

12500
来自专栏10km的专栏

guava:java:java.util.Map和java.util.Set的Key类型转换

昨天写了一博客《java:java.util.Map和java.util.Set的Key类型转换》,主要是想实现以java.util.MapKey类型转换,今天...

23580
来自专栏机器学习入门

LWC 52:687. Longest Univalue Path

LWC 52:687. Longest Univalue Path 传送门:687. Longest Univalue Path Problem: Given...

23970
来自专栏向治洪

数据结构之线性表

基本概念 线性表(List):由零个或多个数据元素组成的有限序列。 特征: 1.线性表是一个序列。 2.0个元素构成的线性表是空表。 3.线性表中的第一个元素无...

21590
来自专栏小灰灰

JDK容器学习之LinkedHashMap(二):迭代遍历的实现方式

LinkedHashMap 如何保障有序的遍历 前一篇《JDK容器学习之LinkedHashMap (一):底层存储结构分析》 中介绍了LinkedHashM...

37670
来自专栏武培轩的专栏

Java中Set集合是如何实现添加元素保证不重复的?

Java中Set集合是如何实现添加元素保证不重复的? Set集合是一个无序的不可以重复的集合。今天来看一下为什么不可以重复。 Set是一个接口,最常用的实现类就...

40670
来自专栏开发之途

Java集合框架源码解析之HashSet

12840
来自专栏Java爬坑系列

【Java入门提高篇】Day28 Java容器类详解(十)LinkedHashMap详解

  今天来介绍一下容器类中的另一个哈希表———》LinkedHashMap。这是HashMap的关门弟子,直接继承了HashMap的衣钵,所以拥有HashMap...

9220
来自专栏LeetCode

LeetCode <二分搜索>34.Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and...

25650

扫码关注云+社区

领取腾讯云代金券