排重算法的实现

       如果给定一个int型数组，要求输出其中重复的数字，应该大多数人都能够实现。但是如果数组内数据很多，假设有10亿个，那直接在该数组上进行操作时间复杂度O(n*n)就会变得很大。所以可以通过对byte数组进行操作来降低时间复杂度，步骤分为以下几步：

1、将int型数组内的数据通过恰当的变换赋值给byte数组：int[i]/8为byte数组的下标，int[i]%8的累加赋值给byte【int[i]/8】；

2、对byte数组进行循环判断：如果byte【int[i]/8】为0，说明byte【int[i]/8】中还未赋值，进入赋值步骤，将byte【int[i]/8】转换成8位二进制；否则进入byte【int[i]/8】二进制和int[i]%8二进制的比较，匹配1则输出，否则对其赋值。

/**
	 * 排重的方法
	 */
	public void Repitation_exlusion(int[] in,int n){
		int[] a = {1,2,4,8,16,32,64};
		char c = '0';
		//byte型数组
		byte[] bytes = new byte[125];
		//byte型数组转换成二进制字符串
		String[] s1 = new String[125];
		//c1用来存放对应byte数组8位二进制字符串
		char[][] c1 = new char[125][8];
		
		//排重
		for(int i=0;i<n;i++){
			//如果byte数组某一项未出现过则为其赋值
			if(c1[in[i]/8]==null){
				switch (in[i]%8) {
				case 0:
					bytes[in[i]/8]+=(byte)a[0];
					break;
				case 1:
					bytes[in[i]/8]+=(byte)a[1];
					break;
				case 2:
					bytes[in[i]/8]+=(byte)a[2];
					break;
				case 3:
					bytes[in[i]/8]+=(byte)a[3];
					break;
				case 4:
					bytes[in[i]/8]+=(byte)a[4];
					break;
				case 5:
					bytes[in[i]/8]+=(byte)a[5];
					break;
				case 6:
					bytes[in[i]/8]+=(byte)a[6];
					break;
				case 7:
					c = '1';
					break;
				default:
					break;
				}
			s1[in[i]/8] = ToBinary8(bytes[in[i]/8]);
			s1[in[i]/8].getChars(1,8,c1[in[i]/8],1);
			c1[in[i]/8][0] = c;
			c='0';
			}
			//byte数组中某一项出现了则进行判断
			else {
				if(c1[in[i]/8][7-in[i]%8]=='1')
					System.out.println(in[i]+"重复出现");
				else{
					if(in[i]%8!=7){
						bytes[in[i]/8]+=(byte)a[in[i]%8];
					}
					else {
						c1[in[i]/8][0]='1';
					}
					s1[in[i]/8] = ToBinary8(bytes[in[i]/8]);
					s1[in[i]/8].getChars(1,8,c1[in[i]/8],1);
				}
			}
			}
			
	}

 

/**
	 * 二进制字符串左补0的方法，将字符串转换成8位二进制数
	 * @param value
	 */
	public  String ToBinary8(int value){
		char[] chars = new char[8];
		value = value & 0xFF;
		for(int i=7;i>=0;i--){
			chars[i] = (value%2==1)?'1':'0';
			value/=2;
		}
		return new String(chars);
		
	}

          遇到的问题：将128赋给byte数组时，发生了越界的情况，因为byte范围是-128~127，所以另外指定一个字符存储。

 改进的代码：

public class RepitationE {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		RepitationE re = new RepitationE();
		//存放整型数据的int型数组
		 int[]in={233,56,789,213,6,0,9,871,11,22,56,33,12,11,78,90,999,88,111,345,90,233,122,4,66,
				667,33,32,54,47,2};
		re.Repitation_exlusion(in,31);
	}
	
	/**
	 * 排重的方法
	 */
	public void Repitation_exlusion(int[] in,int n){
		//byte型数组,行数为整除数，列数为余数
		byte[][] bytes = new byte[125][8];	
		//排重
		for(int i=0;i<n;i++){
			//如果byte数组某一项未出现过则为其赋值
			if(bytes[in[i]/8]==null){
				bytes[in[i]/8][in[i]%8]=1;
			}
			//byte数组中某一项出现了则进行判断
			else {
				if(bytes[in[i]/8][in[i]%8]==1)
					System.out.println(in[i]+"重复出现");
				else{
					bytes[in[i]/8][in[i]%8]=1;
				}
			}
			}
			
	}
}

 

        这样一来不仅免去了创建多个类型数组的麻烦，同时省去了将byte数组内先赋值后转换成二进制的麻烦，代码也简便了很多。