【LeetCode】136.只出现一次的数字（三种解法）
问题描述
这是LeetCode上的一道算法题，笔者整理了三种解题思路和方法，希望可以帮助大家提升算法的思维。
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1] 输出: 1 示例 2:
输入: [4,1,2,1,2] 输出: 4
来源：力扣（LeetCode） 链接：136.只出现一次的数字
一、 解法1（双指针双引用暴力求解）：
注意题设，不能使用额外空间来求解，那么就不用想着用Map求解了。首先给出一个时间复杂度为O（n*n）的算法。 设置2个指针i和j，双重for循环遍历，用计数器变量count记录每个数字出现的次数，代码如下：
public static void main(String[] args) {
int[] arr = new int[]{3,2,3,4,6,6,2};
int resilt = find(arr);
System.out.println(resilt);
}
private static int find(int[] arr) {
for (int i =0;i<arr.length;i++) {
int count=0;
for (int j = 0; j <arr.length; j++) {
if (arr[i]==arr[j]){
count++;
}
}
if (count==1){
return arr[i];
}
}
return -1;
}
内循环结束，刷新count计数器的值，记录每个元素出现的次数，当循环遍历一次之后发现当前元素count为1（只出现一次）时，返回这个值。
二、解法2（排序后与左右元素比较）
先调用Arrays工具类里面的sort排序算法，排序算法最快最优的时间复杂度也得是O（nlogn），排好序后，若这个数字和左右相邻的数字都不一样，就返回这个值。（第一个元素和最后一个元素单独考虑）。代码如下：
public static void main(String[] args) {
int[] arr = new int[]{3,2,3,4,6,6,2};
int resilt = find(arr);
System.out.println(resilt);
}
private static int find(int[] arr) {
if (arr.length == 1)
return arr[0];
Arrays.sort(arr);
//第一个和最后一个单独考虑
if (arr[0] != arr[1])
return arr[0];
if (arr[arr.length - 1] != arr[arr.length - 2])
return arr[arr.length - 1];
for(int i = 1; i < arr.length - 1; i++){
if(arr[i] != arr[i + 1] && arr[i] != arr[i - 1])
return arr[i];
}
return -1;
}三、解法3（异或运算巧解）
下面介绍一个官方给出的时间复杂度只有O（n）的算法。（要是能自己想的出来这个方法的都是大佬~）。 先引出异或运算的定义：
异或（eor）是一个数学运算符。.它应用于 逻辑运算 。.异或的数学符号为"⊕"，计算机符号为"eor"。.其运算法则为： 如果a、b两个值不相同，则异或结果为1。.如果a、b两个值相同，异或结果为0。 异或也叫半加运算，其运算法则相当于不带进位的二进制加法：二进制下用1表示真，0表示假，则异或的运算法则为：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同为0，异为1），这些法则与 加法是相同的，只是不带进位，所以异或常被认作不进位加法。 异或运算的特征：
- 任何数和 0 做异或运算，结果仍然是原来的数，即 a ⊕ 0=a。
- 任何数和其自身做异或运算，结果是 00，即 a ⊕ a=0。
- 异或运算满足交换律和结合律，即 a ⊕ b ⊕ a = b ⊕ a ⊕ a = b ⊕ (a ⊕ a)= b ⊕ 0 = b
这是一个按位异或的运算过程，比如3的二进制位是0011，1的二进制位是0001，那么1⊕ 3 =0011⊕0001=0010=2。 最关键的是，要是两个数相同，异或结果为0！！ 那么这题的思路就来了：把所有数字都做异或运算，那么最后的结果一定是单独的最后那个数字（异或运算满足交换律和结合律），例如这题 ：3⊕2⊕3⊕4⊕6⊕6⊕2 =（3⊕3）⊕（2⊕2）⊕（6⊕6）⊕4 = 0⊕4=4 代码如下：
public static void main(String[] args) {
int[] arr = new int[]{3, 2, 3, 4, 6, 6, 2};
int resilt = find(arr);
System.out.println(resilt);
}
private static int find(int[] arr) {
int ret = 0;
for (int i : arr) {
ret ^= i;
}
return ret;
}四、总结
以上就是笔者整理的三种解题思路，若对老铁们的编程思维有所突破，别忘了一键三连噢(●ˇ∀ˇ●)。
腾讯云开发者
