在一个无序数组中找到3个数字组成数最小,要求这三个数字的索引是按序排列,
有不对的请直接与博主沟通。javascript
/* 从一组无序数中找到组合最小的N位数。 时间复杂度和空间复杂都都N*M,N为位数(三位数N=3),M为数组长度 若是不使用Arrays.copyOf能够进一步改善空间复杂度 input:2315628 output:128 input:23156 output:156 */ import java.util.Arrays; public class FindSmallestN { //结果集 private int[] res ; //结果集指针 private int resIndex = 0; //结果位数 private int N; public void init(int N){ this.N = N; this.res = new int[N]; } /* 对外接口 */ public int[] FIndSmallestN(int[] org){ return this.FIndSmallestN(org,N); } /* 内部业务逻辑 */ private int[] FIndSmallestN(int[] org,int N){ //异常处理 if(org.length<N){ throw new IllegalArgumentException("数组长度小于"+N); } //终止条件 if(N<=0) return null; //剩下的位数恰好够填满结果集 if(org.length==N) { for (int i = 0; i < org.length; i++) { res[resIndex] = org[i]; resIndex++; } return res; } //找到当前位最小的值,注意保证剩下的元素够填满结果集 int min = Integer.MAX_VALUE; int index = 0; for (int i = 0; i <= org.length-N; i++) { if(org[i]<min) { min=org[i]; index = i; } } res[resIndex] = min; resIndex++; //递归填满下一位 this.FIndSmallestN(Arrays.copyOfRange(org,index+1,org.length),N-1); return res; } public static void main(String[] args) { //int[] arr = {2,3,1,5,6,2,8}; //int[] arr = {2,3,1,5,6}; //int[] arr = {1,2,3}; //int[] arr = {3,2,1}; //int[] arr = {1,2}; int[] arr = {8,7,3,2,1}; FindSmallestN FST = new FindSmallestN(); FST.init(4); int[] SmallestN = FST.FIndSmallestN(arr); System.out.println(Arrays.toString(SmallestN)); } }