有1至10w的顺序的数字,从中任意去掉两个之后打乱,然后找到被去掉的这两个数字
package test; import java.util.Random; public class TestSortFind { public static void main(String[] args) { // TODO Auto-generated method stub int n = 100000; int[] a = new int[n]; for(int i = 0; i < n; i++) { a[i] = i; } Random rand = new Random(); int n1 = rand.nextInt(n); int n2 = rand.nextInt(n); while(n1 == n2) { n2 = rand.nextInt(n); } int a1 = a[n1]; int a2 = a[n2]; System.out.println("n1="+n1+" a1="+a1+" n2="+n2+" ,a2="+a2); int[] b = new int[n - 2]; int count = 0; for(int i = 0; i < n; i++) { if(i == n1 || i == n2) { continue; } // System.out.println(i); b[count++] = i; } int x1 = rand.nextInt(b.length); int x2 = rand.nextInt(b.length); int temp = b[x1]; b[x1] = b[x2]; b[x2] = temp; long start = System.currentTimeMillis(); int[] newdata = sort(b, b.length); long end = System.currentTimeMillis(); System.out.println(" time is " + (end - start) + " ms----------------------------------------- "); for(int i = 0; i < newdata.length; i++) { if(i == 0) { if(newdata[0] != a[0]) System.out.println("find=====================" + a[0]); } else{ int d1 = newdata[i - 1] + 1; int d2 = newdata[i]; while(d1 != d2) { System.out.println("find-------------"+d1); d1 += 1; } } if(i == (newdata.length - 1) && (newdata[newdata.length - 1] + 1) == a[n-2]) { System.out.println("find===============" + a[n-2]); } if(i == (newdata.length - 1) && newdata[newdata.length - 1] != a[n - 1]) { System.out.println("find===============" + a[n-1]); } } } /** * 使用归并排序对数组排序 * @param data * @param n * @param max * @return */ private static int[] sort(int[] data, int n){ int[] newdata = new int[n]; if(n > 2) { int mid = n/2; int[] a1 = new int[mid]; System.arraycopy(data, 0, a1, 0, mid); int[] a2 = new int[n - mid]; System.arraycopy(data, mid, a2, 0, n-mid); int[] nd1 = sort(a1,a1.length); int[] nd2 = sort(a2, a2.length); //将打乱的数据归并整理 for(int i = 0; i < nd1.length; i++) { for(int j = 0; j < nd2.length; j++) { if(nd1[i] > nd2[j]) { int temp = nd1[i]; nd1[i] = nd2[j]; nd2[j] = temp; } } } //对小数组进行排序 for(int i = 0; i < nd1.length - 1; i++) { for(int j = i+1; j < nd1.length; j++) { if(nd1[i] > nd1[j]) { int temp = nd1[i]; nd1[i] = nd1[j]; nd1[j] = temp; } } } for(int i = 0; i < nd2.length - 1; i++) { for(int j = i+1; j < nd2.length; j++) { if(nd2[i] > nd2[j]) { int temp = nd2[i]; nd2[i] = nd2[j]; nd2[j] = temp; } } } for(int i = 0; i < nd1.length; i++) { newdata[i] = nd1[i]; } for(int j = 0; j < nd2.length; j++) { newdata[nd1.length + j] = nd2[j]; } } else if(data.length > 1){ if(data[0] > data[1]) { newdata[0] = data[1]; newdata[1] = data[0]; } else { newdata = data; } } else { newdata = data; } return newdata; } }