小算法。求教

Question

最近离职在家，面试出现的一个算法。     
输出一个数组 第n小的值；
题目就这么简单，我也算是搞出来了，但是我是用最传统的  重新排序，然后 输出。 
面试人员说这个方法不是他要的。 很明显 是要优化算法。
在次，望各位大神指教。另外 最近辞职，求职中。有南京的朋友帮忙推荐一下.技能： J2SE ，J2ME ,Android,之前是做手机游戏的，所以 安卓这块只运用过Activity ，想转安卓应用。

Answer 1

在huawei面过同样问题！！！要求循环次数最少。。 结果和楼主一样。。

Answer 2

直接用arrays中的sort方法，然后直接取第几个就可以啊，不是楼上说的用到循环，除非是要你自己写一个算法，不使用jdk中本身自带的方法。

Answer 3

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]);
}

Answer 4

倒序冒泡，N次过后得到想要的值，应该比较快吧。运行一下，看规律就知道了： 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();
}
}

Answer 5

弄个临时数组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,都大于我这里的算法复杂度

Answer 6

要么这么考虑，数组随即取一个数N1，遍历剩余的数，凡是比N1小的数放左边，凡是比N1大的数放右边，然后比较左边的数组的长度加上1和要求的最小n，3种情况：
1.相等，那N1就是所求的数。
2.大于，那说明所求的数在左边的数组，对左边的数组重复之前的步骤，直到得到情况1。
3.小于，说明所求数在右边的数组，在考虑之前的长度的情况下，对右边的数组重复之前的步骤，直到得到情况1。
因为除非是最坏的情况，不会所有的数排序就能得到结果，应该比一般的排序求的方法步骤少。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);
}}

Answer 7

倒序冒泡，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();
        }
    }
 

Answer 8

应该先判断数组size与n的关系吧，然后决定到底是找第n小的还是找第（size-n+1）大的。

Answer 9

这个就是所谓的 nth element 问题
用的是快排的思想
时间复杂度是 O(n) 的