题目

给定一个整数数组，除了某个元素外其余元素均出现两次。请找出这个只出现一次的元素。

备注：

你的算法应该是一个线性时间复杂度。你可以不用额外空间来实现它吗？

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(nlogn)，然后通过一次遍历循环找到只出现一次的数字。这段代码跑了7ms，仅超过32.86%的java提交。

class Solution {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i += 2) {
            if (nums[i] != nums[i - 1]) {
                return nums[i - 1];
            }
        }
        return nums[nums.length - 1];
    }
}

异或运算

仔细看题目，可以发现，题目要求达到一个线性时间复杂度，并且要求不使用额外空间。认真思考一下，结合逻辑运算，相同元素进行异或运算结果为0，任何元素与0异或不变。利用异或运算的这种性质，我们只需要用foreach对数组进行一次循环遍历，异或所有元素，便可以筛选出只出现一次的元素。这段代码跑了1ms，超过100%的java提交，非常nice。

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int i :
                nums) {
            result ^= i;
        }
        return result;
    }
}

结语

对于第一种方法运用到的排序是直接调用Arrays类的静态方法sort()，然后就发现自己已经对7种基本的排序算法十分生疏了，需要重新总结一下它们。第二种方法发现运用逻辑运算、位移等操作能够极大地提高程序速度，遇到难解的问题时，可以考虑考虑这些少见的操作方式，可能会有奇效。Last but not least, keep coding！