日期:2014-05-20 浏览次数:20650 次
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次过后得到想要的值,应该比较快吧。运行一下,看规律就知道了:
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。
因为除非是最坏的情况,不会所有的数排序就能得到结果,应该比一般的排序求的方法步骤少。
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); } }