只出现一次的数字

Get to learn something new ! exclusive OR

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

说明：

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

示例:

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

示例 2:

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

我的

   func singleNumber(_ nums: [Int]) -> Int {
        var returnNum = 0
        for i in 0..<nums.count{
        returnNum = returnNum^nums[i]
        }
        return returnNum
    }

异或

1^1 = 0 1^1^2 = 2 1^1^2^2^3 = 3 0和任何数异或得其本身

Java

比较法

　　思路：先对数组进行排序，然后对 nums[i] 和 nums[i + 1]进行比较，如相等，i+=2，继续下一组比较，直到取到不相等的一组。

　　注意：首先这个数组的长度肯定是奇数（目标数字只出现一次，其他所有数字出现两次），所以如果上述步骤没有找到不相等的一组数，那么肯定是数组的最后一个数字是单独出现的。 　　

 1　  public static int singleNumber(int[] nums) {
 2         Arrays.sort(nums);  // 排序数组
 3         for (int i = 0; i < nums.length - 1; i += 2) {
 4             // 找到不相等的一组，直接返回
 5             if (nums[i] != nums[i + 1]) {
 6                 return nums[i];
 7             }
 8         }
 9         // 如果没有找到不相等的一组数据，直接返回数组的最后一个数字
10         return nums[nums.length - 1];
11     }

> 方法二（去重法）：

　　思路：利用HashSet的特性，删除重复的数组元素，最后剩下一个单独的元素，返回即可。

1   public static int singleNumber(int[] nums) {
2         Set<Integer> set = new HashSet<>();
3         for (int i = 0; i < nums.length; i++) {
4             if (!set.add(nums[i])) { // add成功返回true，如果set中已有相同数字，则add方法会返回false
5                 set.remove(nums[i]); // 删除重复出现的数字
6             }
7         }
8         return set.iterator().next();9     }

<br/v>

方法三（求差法）：

　　思路：先对数组排序，显而易见的，单独出现一次的数据必然是出现在数组下标为偶数的位置（下标从0开始），那么所有奇数下标的元素之和减去偶数下标的元素之和，就是需要求得的结果。 　　

1     public static int singleNumber(int[] nums) {
2         int num = 0;
3         Arrays.sort(nums);
4         for (int i = 0; i < nums.length; i++) {
5             // 偶数下标位置 num += nums[i]，奇数下标位置 num -= nums[i]
6             num = i % 2 == 0 ? num + nums[i] : num - nums[i];
7         }
8         return num;
9     }