有1至10w的顺序的数字,从中任意去掉两个之后打乱,然后找到被去掉的这两个数字

时间:2022-03-03 13:14:14

有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;
	} 

}