最近离职在家，面试出现的一个算法。
输出一个数组 第n小的值；
题目就这么简单，我也算是搞出来了，但是我是用最传统的 重新排序，然后 输出。
面试人员说这个方法不是他要的。 很明显 是要优化算法。
在次，望各位大神指教。
另外 最近辞职，求职中。有南京的朋友帮忙推荐一下.技能： J2SE ，J2ME ,Android,之前是做手机游戏的，所以 安卓这块只运用过Activity ，想转安卓应用。
------解决方案--------------------
直接用arrays中的sort方法，然后直接取第几个就可以啊，不是楼上说的用到循环，除非是要你自己写一个算法，不使用jdk中本身自带的方法。
------解决方案--------------------
- Java code
public static void main(String[] args) { int[] nums={1,4,66,2,9}; Arrays.sort(nums); int n=3; //第3小的数 System.out.println(nums[n-1]); }
------解决方案--------------------
倒序冒泡，N次过后得到想要的值，应该比较快吧。运行一下，看规律就知道了：
- Java code
public static void main(String[] args) { int[] is = new int[]{1,13,15,2,12,32,14,7,4,0,6,5}; int temp = 0; for(int i = is.length - 1; i >= 1; i--){ for(int j = i - 1; j >= 0; j--){ if(is[i] > is[j]){ temp = is[i]; is[i] = is[j]; is[j] = temp; } } for(int in : is){ System.out.print(in + " "); } System.out.println(); } }
------解决方案--------------------
弄个临时数组a[n];然后遍历目标对象集合,
for(目标数值:目标集合){
和a[n]中的数值进行二分法查找比较:
如果比a[n]中的最大的a[i]大,则:{
如果i是临时数组a[n]的末尾把这个目标数值插到a[i],其他数值都往下标0方向shift(原来最小的就挤掉了)
如果不是则把目标数值添加到a[i+1]
}
如果目标数值介于a[i-1]和a[i]之间则{
把目标数值添加到a[i-1],原来的a[i-1]到a[0]的数值往0方向shift(原来最小的就挤掉了)
}
}
现在a[0]就是top n的值,这里算法O(N)貌似=N*log(n)≈N(n是top n的n,N是目标集合中数值的个数),应该是最小的了,上面用Array.sort的最小算法复杂度是N*log(2N),最坏算法复杂度为N*N,都大于我这里的算法复杂度
------解决方案--------------------
要么这么考虑，数组随即取一个数N1，遍历剩余的数，凡是比N1小的数放左边，凡是比N1大的数放右边，然后比较左边的数组的长度加上1和要求的最小n，3种情况：
1.相等，那N1就是所求的数。
2.大于，那说明所求的数在左边的数组，对左边的数组重复之前的步骤，直到得到情况1。
3.小于，说明所求数在右边的数组，在考虑之前的长度的情况下，对右边的数组重复之前的步骤，直到得到情况1。
因为除非是最坏的情况，不会所有的数排序就能得到结果，应该比一般的排序求的方法步骤少。
- Java code
import java.util.ArrayList;import java.util.List;public class Test21 { /** * @param args */ List<Integer> min=new ArrayList<Integer>(); List<Integer> max=new ArrayList<Integer>(); List<Integer> buff=new ArrayList<Integer>(); int n; int size; private void toList(int size,int...array){ this.size=size; n=array[0]; System.out.print("第"+size+"个小的数:"); for(int i=1;i<array.length;i++){ if(array[i]>n){ max.add(array[i]); } else{ min.add(array[i]); } } while(isResult()!=0){ toListAgain(); } System.out.println(n); } private void toListAgain(){ n=buff.get(0); buff.remove(0); for(int x:buff){ if(x>n){ max.add(x); } if(x<n){ min.add(x); } } } private int isResult(){ buff.clear(); int result=min.size()+1; if(size==result){ return 0; } else if(result>size){ buff.addAll(min); max.clear(); min.clear(); return -1; } else{ size=size-result; buff.addAll(max); max.clear(); min.clear(); return 1; } } public static void main(String[] args) { // TODO Auto-generated method stub int [] array={10,2,54,24,11,69,7,43,33}; new Test21().toList(3, array); }}