题目描述

现在有一个整数类型的数组，数组中素只有一个元素只出现一次，其余的元素都出现两次。

注意：

你需要给出一个线性时间复杂度的算法，你能在不使用额外内存空间的情况下解决这个问题么？

示例1

输入

[复制](javascript:void(0)😉

[1,0,1]

返回值

[复制](javascript:void(0)😉

0

本菜鸡的解题代码

大概思路是暴力对比，暴力就完事了。

二重循环，先提前在外层循环设定一个初始标志，为0，

内存循环 ，如果找到相同的，则将标志设为1。

外层在根据标志判断是否找到相同的，否则返回出不同的值。

public class Solution {
    /**
     * 
     * @param A int整型一维数组 
     * @return int整型
     */
    public int singleNumber (int[] A) {
        // write code here
        for (int i = 0; i<A.length ;i++) {
            int hasSame=0;
            for (int j = 0; j<A.length; j++){
                if(i==j){
                    System.out.println("相同索引  A["+i+"]="+A[i]+" ,i="+i+", j="+j);
                    continue;
                }
                if(A[i]==A[j]){
                    hasSame=1;
                    break;
                }
            }
            if(hasSame==0){
                return A[i];
            }
        }
        return 0;
    }
}

大佬的代码

链接：https://www.nowcoder.com/questionTerminal/0bc646909e474ac5b031ec6836a47768
来源：牛客网

根据异或运算特点：

两个相同的数进行异或，结果为0

	public static int singleNumber(int[] A) {
		int num = 0;
		for(int i=0;i<A.length;i++){
			num^=A[i];
		}
		return num;
	}

其实只要记住：

​ 1.异或满足交换律。

​ 2.相同两个数异或为0。

​ 3.0异或一个数为那个数本身。

最后结果即出现1次的那个数。