找出数组中只出现一次的数字

问题描述：

    一个整型数组里除了一个数字以外，其他数字都出现了两次。找出这个只出现一次的数字

算法思路：

     *    异或运算：任何一个数字异或它本身都等于0,
     *    如果从头到尾异或数组中的每一个数字，那些出现两次的数字全部在异或中会被抵消，
     *    最终的结果刚好是这个只出现一次的数字

package JBArray;

/**
 * 找出数组中只出现一次的数字
 * @author Dan
 *
 */
public class FindOnce {
	
	/**
	 * 问题描述：
	 *    一个整型数组里除了一个数字以外，其他数字都出现了两次。找出这个只出现一次的数字
	 * 算法思路：
	 *    异或运算：任何一个数字异或它本身都等于0,
	 *    如果从头到尾异或数组中的每一个数字，那些出现两次的数字全部在异或中会被抵消，
	 *    最终的结果刚好是这个只出现一次的数字
	 * @param a
	 * @return
	 */
	public static int findNotDouble(int a[]){
		int n = a.length;
		int result = a[0];
		int i;
		for(i=1;i<n;++i){
			result ^= a[i];
		}
		return result;
	}

}

 问题描述：

一个数组里除了一个数字之外，其他数字出现了n次，那么该如何找出这个数字呢？

1、先求出每一位出现1的个数

2、每一位个数整除n

优点：适用于奇数次或偶数次

图解：

代码实现：

/**
	 * 问题描述：一个数组里除了一个数字之外，其他数字出现了n次，那么该如何找出这个数字呢？
	 * @param a
	 * @param appearTimes
	 * @return
	 */
	public static int findOnce(int a[], int appearTimes){
		int n = a.length;
		int[] bitCount = new int[32];
		//计算数组中所有数组对应的二进制数各个位置出现1的次数
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 32; j++) {
				bitCount[j] += ((a[i]>>j)&1);
			}
		}
		//若某位上的结果不能被整除，则肯定目标数字在这一位上
		int appearOne = 0;
		for (int i = 0; i < 32; i++) {
			if (bitCount[i]%appearTimes != 0 ) {
				appearOne += (1<<i);
			}
		}
		return appearOne;
	}

测试代码：

	public static void main(String[] args) {
		int[] arr1 = {1,2,2,3,3,1,4};
		int[] arr2 = {1,2,1,2,4,2,4,4,1,3};
		int num = findNotDouble(arr1);
		int num1 = findOnce(arr2, 3);
		System.out.println(num);
		System.out.println(num1);
	}

最后

以上就是靓丽高山为你收集整理的找出数组中只出现一次的数字的全部内容，希望文章能够帮你解决找出数组中只出现一次的数字所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。