Single Number：从数组中找出只出现一次的数字

[ 问题: ]

Given an array of integers, every element appears twice except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

翻译：给定一个整数数组，数组中所有元素都出现了两次，只有一个元素只出现了一次，找出这个只出现了一次的元素。

[ 解法: ]

①. 常规解法：时间复杂度为O(n)，没能通过

/**
 * Time Limit Exceeded
 * 时间复杂度为:O(n)，无法通过
 */
public class Solution1 {
    public int singleNumber(int[] arr) {
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (arr[i] == arr[j]) {
                    count++;
                }
            }
            if (count == 1) {
                return arr[i];
            } else {
                count = 0;
            }
        }
        return -1;
    }  

    public static void main(String[] args) {
        int[] arr = { 0, 1, 1, 2, 2, 3, 0 };
        System.out.println(new Solution1().singleNumber(arr));
    }
}

②. 标准解法：使用异或运算

更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

这个程序用了个小技巧：一个整数和它本身异或之后得到值是0，0与其他整数异或得到的是这个整数本身

/**
 * 利用异或的可交换性
 */
public class Solution2 {
    public int singleNumber(int[] arr) {
        // invalid check
        if (arr.length == 0) {
            return -1;
        }
        int result = 0;
        for (int i = 0; i < arr.length; i++) {
            result = result ^ arr[i];
        }
        return result;
    }  

    public static void main(String[] args) {
        int[] arr = { 0, 1, 1, 2, 2, 3, 0 };
        System.out.println(new Solution2().singleNumber(arr));
    }
}

[ 拓展:]

异或运算的两个法则：

①. a ^ b = b ^ a

②. a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c

真 ^  假 = 真　　假 ^  真 = 真　　假 ^  假 = 假　　真 ^  真 = 假

/**
 * 不使用第三个变量,交换两个变量的值
 */
public class Swap {
    public static void main(String[] args) {
        int a = 1, b = 2;
        System.out.println("交换前: a = " + a + " , b = " + b);
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
        System.out.println("交换后: a = " + a + " , b = " + b);
    }
}

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索数组
， int
， 异或
， 整数
， public
， arr
解法
single韩剧、single是什么意思、sing、signal、single dog，以便于您获取更多的相关知识。