问题内容:
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
示例1:
输入: [2,2,1] |
输出: 1 |
示例2:
输入: [4,1,2,1,2] |
输出: 4 |
方法一:暴力求解法
这是最直观的一种求法,每次取数组中的一个数,通过计数来判断这个数的个数是否为1,有则返回这个元素,无则返回-1。
代码实现:
public static int appearOneNumber1(int[] arr){ for (int i = 0; i < arr.length; i++) { int count = 0; int temp = arr[i]; for (int j = 0; j < arr.length; j++) { if (arr[j] == temp){ count++; } } if (count == 1){ return temp; } } return -1; }
此方法虽然直观,但是代码麻烦,运行时间也相对下面求法长。
方法二:异或求解法
异或的特点是:
1、n ^ n = 0;即两个相同的数字异或是0
2、0 ^ n = n;即0和任何数字进行异或,结果就是那个任何数字。
因此将数组遍历异或,最终的结果就是个数为一的数。
代码实现:
public static int appearOneNumber(int[] arr){ int temp = 0; //此处for循环为增强型for循环 for (int i : arr) { temp ^= i; } return temp; }