1.排序

1.选择排序 O(n2)

	public static void selectionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		// 0 ~ N-1  找到最小值，在哪，放到0位置上
		// 1 ~ n-1  找到最小值，在哪，放到1 位置上
		// 2 ~ n-1  找到最小值，在哪，放到2 位置上
		for (int i = 0; i < arr.length - 1; i++) {
			int minIndex = i;
			for (int j = i + 1; j < arr.length; j++) { // i ~ N-1 上找最小值的下标 
				minIndex = arr[j] < arr[minIndex] ? j : minIndex;
			}
			swap(arr, i, minIndex);
		}
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

2.冒泡排序 O(n2)

	public static void bubbleSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		// 0 ~ N-1
		// 0 ~ N-2
		// 0 ~ N-3
		for (int e = arr.length - 1; e > 0; e--) { // 0 ~ e
			for (int i = 0; i < e; i++) {
				if (arr[i] > arr[i + 1]) {
					swap(arr, i, i + 1);
				}
			}
		}
	}

	// 交换arr的i和j位置上的值
	public static void swap(int[] arr, int i, int j) {
		arr[i] = arr[i] ^ arr[j];
		arr[j] = arr[i] ^ arr[j];
		arr[i] = arr[i] ^ arr[j];
	}

3.插入排序

//保证0-i个数有序
	public static void insertionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		// 不只1个数
		for (int i = 1; i < arr.length; i++) { // 0 ~ i 做到有序
			for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
				swap(arr, j, j + 1);
			}
		}
	}

	// i和j是一个位置的话，会出错
	public static void swap(int[] arr, int i, int j) {
		arr[i] = arr[i] ^ arr[j];
		arr[j] = arr[i] ^ arr[j];
		arr[i] = arr[i] ^ arr[j];
	}

1. 异或运算题目

1.交换两个数 不通过第三个数

以下两个结果一样

		b = a ^ b;
		a = a ^ b;
		b = a ^ b;

		a = a ^ b;
		b = a ^ b;
		a = a ^ b;

2. 只有1个出现奇数次的数

一个数组中一个数出现了奇数次，其他数都出现了偶数次，找到这个数

	// arr中，只有一种数，出现奇数次
	public static void printOddTimesNum1(int[] arr) {
		int eor = 0;
		for (int i = 0; i < arr.length; i++) {
			eor ^= arr[i];
		}
		System.out.println(eor);
	}

3.找出int型数据二进制格式种最右侧的1

	public static int bit1counts(int N) {
		int count = 0;
		
		//   011011010000
		//   000000010000     1
		
		//   011011000000
		// 

		while(N != 0) {
			//取反加1也就是自己的相反数
			int rightOne = N & ((~N) + 1); //~N 取反
			count++;
			N ^= rightOne;
			// N -= rightOne
		}

		return count;
		
	}

4.有2个出现奇数次的数

一个数组中2个数出现了奇数次，其他数都出现了偶数次，找到这2个数

//假设这2个数是a和b
	// arr中，有两种数，出现奇数次
	public static void printOddTimesNum2(int[] arr) {
		int eor = 0;
		for (int i = 0; i < arr.length; i++) {
			eor ^= arr[i];   //eor最后是a^b的结果
		}
		// a 和 b是两不相等的数，所以 eor != 0 
		// 提取出来 eor 二进制格式种最右侧的1, 
		//最右侧的为1说明，a和b二进制格式种这以为不相等,
		//以此为标准将数据种的数据划分成两类，分别异或，每类即只包含一个出现寄数次的数
		// eor :     00110010110111000
		// rightOne :00000000000001000
		int rightOne = eor & (-eor); // 提取出最右的1
		
		int onlyOne = 0; // eor'
		for (int i = 0 ; i < arr.length;i++) {
			//  arr[1] =  111100011110000
			// rightOne=  000000000010000
			if ((arr[i] & rightOne) != 0) {
				onlyOne ^= arr[i];  //最后提取一个
			}
		}
		//a^b^a=b
		System.out.println(onlyOne + " " + (eor ^ onlyOne));
	}

5.

一个数组种有一种数出现了K次，其他数都出现M次，
M>1, k<M
找到出现了K次的数
要求，额外空间复杂度为O(1)，时间复杂度0(n)

	// 请保证arr中，只有一种数出现了K次，其他数都出现了M次
	public static int onlyKTimes(int[] arr, int k, int m) {
		if (map.size() == 0) {
			mapCreater(map);
		}
		int[] t = new int[32];
		//用一个长度为32的数据保存每个数二进制格式种对应位置1的个数，
		//如果某个位置1的个数与M取模等0，说明出现出现1的个数是M的整数被，即二进制格式种此位置出现K次的那个数为0
		// 如果取模等于K ,说明二进制格式种此位置出现K次的那个数为1
		// t[0] 0位置的1出现了几个
		// t[i] i位置的1出现了几个

		//用一个长度为32的数据保存每个数二进制格式种对应位置1的个数
		for (int num : arr) {
			for(int i= 0; i < 32; i++) {
				t[i] += (num >> i ) & 1;
			}
			
/*			while (num != 0) {
				int rightOne = num & (-num);
				t[map.get(rightOne)]++;
				num ^= rightOne;
			}*/
		}
		int ans = 0;
		//取模计算出现k次数
		for (int i = 0; i < 32; i++) {
			if (t[i] % m != 0) {
				if (t[i] % m == k) {
					ans |= (1 << i);
				} else {
					return -1;
				}
			}
		}
		
		//出现K次数是0这个数情况
		if (ans == 0) {
			int count = 0;
			for (int num : arr) {
				if (num == 0) {
					count++;
				}
			}
			if (count != k) {
				return -1;
			}
		}
		return ans;
	}