剑指offer-例题最小的k个数

题目描述

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

解法一：

快速排序后取前k个元素即为最小的k个数

时间复杂度：O(nlogn)

空间复杂度：O(n)

需要改变数组，适用于允许数组发生改变的情况

import java.util.ArrayList; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { ArrayList<Integer> result=new ArrayList<Integer>(); if(input==null||input.length==0||k<=0) return result; if(k>input.length) return result; quickSort(input,0,input.length-1); for(int i=0;i<k;i++) result.add(input[i]); return result; } public void quickSort(int[] input,int start,int end) { if(input==null||input.length==0||start>end) return; int num=input[start]; int i=start; int j=end; while(i<j) { while(i<j&&input[j]>=num) j--; while(i<j&&input[i]<=num) i++; if(i<j) { int temp=input[i]; input[i]=input[j]; input[j]=temp; } } input[start]=input[i]; input[i]=num; quickSort(input,start,i-1); quickSort(input,i+1,end); } }

不要漏掉k>input.length的异常情况

解法二：

快速排序算法的扩展：只将k之前数组元素排好序

时间复杂度：O(nlogn)

空间复杂度：O(n)

需要改变数组，适用于允许数组发生改变的情况

import java.util.ArrayList; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { ArrayList<Integer> result=new ArrayList<Integer>(); if(input==null||input.length==0||k<=0) return result; if(k>input.length) return result; int start=0; int end=input.length-1; int index=findIndex(input,start,end); int t=k-1; while(index!=t) { if(index>t) index=findIndex(input,start,index-1); else index=findIndex(input,index+1,end); } //前k个元素一定已经排好序了 for(int i=0;i<k;i++) result.add(input[i]); return result; } public int findIndex(int[] input,int start,int end) { if(input==null||input.length==0||start>end) return -1; int num=input[start]; int i=start; int j=end; while(i<j) { while(i<j&&input[j]>=num) j--; while(i<j&&input[i]<=num) i++; if(i<j) { int temp=input[i]; input[i]=input[j]; input[j]=temp; } } input[start]=input[i]; input[i]=num; return i; } }

解法三：最大堆

堆排序

先将数组中的前k个元素取出放入容器中，比较剩余元素与容器中最大值的大小，如果小于则应该从容器中将最大值替换为剩余元素，由于每次都需要找容器中的最大值，因此将该容器设计为最大堆，并借助堆排序

时间复杂度：O(nlogk)

空间复杂度：O(k)

import java.util.ArrayList; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { ArrayList<Integer> result=new ArrayList<Integer>(); ArrayList<Integer> array=new ArrayList<Integer>(); if(input==null||input.length==0||k>input.length||k<=0) return result; //先取前k个存入数组中 for(int i=0;i<k;i++) { addValue(array,input[i]); } for(int i=k;i<input.length;i++) { if(input[i]<array.get(0)) { removeValue(array); addValue(array,input[i]); } } for(int i=array.size()-1;i>=0;i--) result.add(array.get(i)); return result; } //向堆中添加元素 public void addValue(ArrayList<Integer> array,int value) { if(array==null) return; array.add(value); int i=array.size()-1; while(i>=1&&value>array.get((i-1)/2)) { array.set(i,array.get((i-1)/2)); array.set((i-1)/2,value); i=(i-1)/2; } } //删除堆顶元素 public void removeValue(ArrayList<Integer> array) { if(array==null||array.size()==0) return; array.set(0,array.get(array.size()-1)); array.remove(array.size()-1); int i=0; while(2*i+1<array.size()) { int value=array.get(i); int a=array.get(2*i+1); int max=a; int index=2*i+1; //左右孩子都存在 if(2*i+2<array.size()) { int b=array.get(2*i+2); if(b>a) { max=b; index=2*i+2; } } if(value<max) { array.set(i,max); array.set(index,value); i=index; } else break; } } }