日期:2014-05-20  浏览次数:20650 次

小算法。求教
最近离职在家,面试出现的一个算法。  
输出一个数组 第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);
            

    }

}