给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

解法一：

不排序，直接使用双重 for 循环进行查找。

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        int temp;
        int flag;
        for(int i = 0;i<nums.length;i++){
            flag = 1;
            temp = nums[i];
            for(int j = 0;j<nums.length;j++){
                if(i!=j && temp == nums[j]){
                    flag = 0;
                    break;
                }
            }
            if(flag == 1){
                ans = nums[i];
                break;
            }
        }
                        return ans;

    }
}

解法二：

先排序，再用 for 循环查找，如果当前元素和下一个元素不相同，则当前元素就是要找的数字，如果遍历到最后一个元素，则该元素为所求。

class Solution {
    public int singleNumber(int[] nums) {

        Arrays.sort(nums);
        int ans = nums[0];
        for (int i = 0; i < nums.length; i = i + 2) {

            if (i == nums.length - 1 || nums[i] != nums[i + 1]) {
                ans = nums[i];
                break;
            }
        }
        return ans;
    }
}

解法三：

使用位运算。在异或运算中，任何一个数字和自己本身异或都是 0，任何一个数字和 0 异或都是本身。所以，如果数组存在一个只出现一次的数字，那么该数组所有元素的异或结果就是该数字。

class Solution {
    public int singleNumber(int[] nums) {
        int temp = 0;
        for(int i = 0;i<nums.length;i++){
            temp ^=nums[i];
        }
        return temp;

    }
}