牛客--剑指offer--最小的k个数

一、问题描述

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

二、解题思路

主要是考察排序，本题实现了常用的插入排序，堆排序，归并排序，其中堆排序（最小堆）应该是速度最快的。

三、代码

1.插入排序

import java.util.*; 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>input.length) return result; int j; for(int i=1;i<input.length;i++){ int tmp=input[i]; for(j=i;j>0 && tmp-input[j-1]<0;j--) input[j]=input[j-1]; input[j]=tmp; } for(int i=0;i<k;i++) result.add(input[i]); return result; } }

2.归并排序

import java.util.*; 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>input.length) return result; int[] tmp=new int[input.length]; mergeSort(input,tmp,0,input.length-1); for(int i=0;i<k;i++) result.add(input[i]); return result; } private void mergeSort(int[] a,int[] tmp,int left,int right){ if(left<right){ int middle=left+(right-left)/2; mergeSort(a,tmp,left,middle); mergeSort(a,tmp,middle+1,right); merge(a,tmp,left,middle+1,right); } } private void merge(int[] a,int[] tmp,int leftpos,int rightpos,int rightend){ int leftend=rightpos-1; int numelements=rightend-leftpos+1; int tmppos=leftpos; while(leftpos<=leftend && rightpos<=rightend){ if(a[leftpos]<a[rightpos]) tmp[tmppos++]=a[leftpos++]; else tmp[tmppos++]=a[rightpos++]; } while(leftpos<=leftend){ tmp[tmppos++]=a[leftpos++]; } while(rightpos<=rightend) tmp[tmppos++]=a[rightpos++]; for(int i=0;i<numelements;i++,rightend--) a[rightend]=tmp[rightend]; } }3.堆排序（最小堆）

import java.util.*; 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>input.length) return result; for(int i=input.length/2;i>=0;i--){ percDown(input,i,input.length); } for(int i=input.length-1;i>=(input.length-k);i--){ result.add(input[0]); swapReference(input,0,i); percDown(input,0,i); } return result; } private void percDown(int[] input,int i,int n){ int child=0; int tmp; for(tmp=input[i];leftChild(i)<n;i=child){ child=leftChild(i); if(child!=n-1 && input[child]>input[child+1]) child++; if(tmp>input[child]) input[i]=input[child]; else break; } input[i]=tmp; } private int leftChild(int n){ return 2*n+1; } private void swapReference(int[] input,int i,int j){ int tmp=input[i]; input[i]=input[j]; input[j]=tmp; } }

使用快排的思想排序

import java.util.*; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { ArrayList<Integer> result = new ArrayList<Integer>(); if(input == null || k > input.length) return result; quickSort(input,0,input.length-1); for(int i=0;i<k;i++){ result.add(input[i]); } return result; } private void quickSort(int[] a,int left,int right){ if(right-left>=2){ int median = getMedian(a,left,right); int i = left; int j = right-1; for(;;){ while(a[++i]<median){ } while(a[--j]>median){ } if(i<j){ swap(a,i,j); }else{ break; } } quickSort(a,left,i-1); quickSort(a,j+1,right); }else if(left < right && a[left]>a[right]){ swap(a,left,right); } } private void swap(int[] a,int i,int j){ int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } private int getMedian(int[] a,int i,int j){ int tmp; int median = i + (j-i)/2; if(a[i]>a[j]){ tmp = a[i]; a[i] = a[j]; a[j] = tmp; } if(a[i]>a[median]){ tmp = a[i]; a[i] = a[median]; a[median] = tmp; } if(a[median]>a[j]){ tmp = a[median]; a[median] = a[j]; a[j] = tmp; } tmp = a[j-1]; a[j-1] = a[median]; a[median] = tmp; return a[j-1]; } }