题目：输入N个整数，找出其中最小的k个整数。例如输入 4,5,1,6,2,7,3,8，输入k=4，则输出最小的四个数是1,2,3,4
算法分析：
算法1.O(n)的算法，修改输入的数组
可以基于getMiddle函数来解决此问题。如果基于数组的第k个数字来调整，使得第k个数字小的所有数字都位于数组的左边，比第k个数字大的所有数字都位于数组的右边。这样调整后，位于数组左边的k个数字就是最小的k个数字。
算法2.O(nlogk)的算法，适合处理海量数据
此种算法需要使用Java中的TreeSet排序并去除重复元素，利用ArrayList存储并输出。
TreeSet原理：TreeSet在存储对象的时候，可以排序，但是需要制定排序的算法。其中的Integer和String都能实现默认的排序顺序。在使用TreeSet存储对象的时候，add（）方法内部就会自动调用compareTo（）方法进行比较，根据比较结果使用二叉树的形式进行存储。
TreeSet是一个有序集合，TreeSet中的元素将按照升序排列，缺省是按照自然排序进行排列，意味着TreeSet中的元素要实现Comparable接口。或者有一个自定义的比较器。
我们可以在构造TreeSet对象时，传递实现Comparator接口的比较器对象。
TreeSet事例代码：
import java.util.Iterator;
import java.util.*
;
public class TreeSetTest {
public static void main(String[] args) {
Set ts =
new TreeSet();
ts.add("abc"
);
ts.add("xyz"
);
ts.add("rst"
);
Iterator it =
ts.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
}
} 输出结果：
abc
rst
xyz
来源： http://www.cnblogs.com/ningvsban/archive/2013/05/06/3062535.html
算法3.冒泡排序
采用冒泡排序的思想，最外层循环k次就可以了，也就是说不用全部排列，只调出符合提议的k个就可以了。
算法1源程序：
[java]
view plain
copy
package org.marsguo.offerproject30; import java.util.Scanner; class FindTheLeastNumber{ public void leastNumberFun(int[] inputarray,int k){ if(inputarray == null || k > inputarray.length || inputarray.length <= 0 || k <= 0) return; int n = inputarray.length; int start = 0; int end = n -1; int index = getMiddle(inputarray,start,end); while(index != k - 1){ if(index > k - 1){ end = index - 1; index = getMiddle(inputarray, start, end); } else{ start = index + 1; index = getMiddle(inputarray, start, end); } } int[] outputarray = new int[k]; for(int i = 0; i < k; ++i){ outputarray[i] = inputarray[i]; } System.out.println("最小的" + k + "个数是："); for(int i = 0; i < k; ++i){ System.out.print(outputarray[i] + ","); } } public int getMiddle(int[] sortArray,int low,int high){ int key = sortArray[low]; while(low<high){ while(low <high && sortArray[high] >= key){ high--; } sortArray[low] = sortArray[high]; while(low < high && sortArray[low] < key){ low++; } sortArray[high] = sortArray[low]; } sortArray[low] = key; return low; } } public class GetLeastNumber { public static void main(String[] args){ Scanner scanner = new Scanner(System.in); System.out.println("请输入一个数组，以空格隔开："); String str = scanner.nextLine(); System.out.println("请输入K的值："); int k = scanner.nextInt(); scanner.close(); String[] temp = str.split(" "); int[] array = new int[temp.length]; for(int i = 0; i<temp.length; i++){ array[i] = Integer.parseInt(temp[i]); } FindTheLeastNumber findnum = new FindTheLeastNumber(); findnum.leastNumberFun(array, k); } }
算法2源程序：
[java]
view plain
copy
package org.marsguo.offerproject30; import java.util.*; public class TreeSetSolution { public static ArrayList<Integer> GetLeastNumbers_Solution(int[] input,int k){ ArrayList<Integer> list = new ArrayList<Integer>(); ArrayList<Integer> list2 = new ArrayList<Integer>(); if(input == null || input.length == 0 || k ==0 || k > input.length) return list; TreeSet<Integer> set = new TreeSet<Integer>(); for(int i = 0 ; i < input.length; i++){ set.add(input[i]); } Iterator<Integer> it = set.iterator(); while(it.hasNext()){ int x = it.next(); list.add(x); } for(int i = 0; i < k; i++){ list2.add(list.get(i)); } return list2; } public static void main(String[] args){ Scanner scanner = new Scanner(System.in); System.out.println("请输入一个数组，以空格隔开："); String str = scanner.nextLine(); System.out.println("请输入K的值："); int k = scanner.nextInt(); scanner.close(); String[] temp = str.split(" "); int[] array = new int[temp.length]; for(int i = 0; i<temp.length; i++){ array[i] = Integer.parseInt(temp[i]); } System.out.println("最小" + k +"个数是：" + GetLeastNumbers_Solution(array,k)); } }
算法3源程序：
[java]
view plain
copy
package org.marsguo.offerproject30; import java.util.ArrayList; import java.util.Scanner; class Solution{ public ArrayList<Integer> GetLeastNumbers_Solution(int[] input,int k){ ArrayList<Integer> al = new ArrayList<Integer>(); if (k > input.length) { return al; } for (int i = 0; i < k; i++) { for (int j = 0; j < input.length - i - 1; j++) { if (input[j] < input[j + 1]) { int temp = input[j]; input[j] = input[j + 1]; input[j + 1] = temp; } } al.add(input[input.length - i - 1]); } return al; } } public class PopSortSolution { public static void main(String[] args){ Scanner scanner = new Scanner(System.in); System.out.println("请输入一个数组，以空格隔开："); String str = scanner.nextLine(); System.out.println("请输入K的值："); int k = scanner.nextInt(); scanner.close(); String[] temp = str.split(" "); int[] array = new int[temp.length]; for(int i = 0; i<temp.length; i++){ array[i] = Integer.parseInt(temp[i]); } Solution solution = new Solution(); System.out.println("最小" + k +"个数是：" +solution.GetLeastNumbers_Solution(array, k)); } }
