136.只出现一次的数字

题目描述

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

说明：

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

示例：

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

思路1

1. 使用快速排序，将相同元素都放在相邻位置上。

2.遍历数组，每次跳跃两个元素进行寻找，若nums[i] != nums[i+1]，说明nums[i]就是答案。

Java代码实现

    public int singleNumber(int[] nums) {
        Arrays.sort(nums);

        for(int i=0;i<nums.length;i=i+2){
            if(i+1 < nums.length && nums[i] != nums[i+1])
                return nums[i];
        }
        return nums[nums.length-1];
    }

思路2

1. 题中除目标元素外，都出现两次，可以利用 相同元素 异或 等于 0 的性质。
2. 最终异或结果即为要寻找的元素。

Java代码实现

    public int singleNumber(int[] nums) {
        int res = nums[0];

        for(int i=1;i<nums.length;i++){
            res = res ^ nums[i];
        }

        return res;
    }