P6 单身数字

描述#

这个题目说的是，给你一个非空的整数数组，这个数组中有一个整数只出现了一次，其它的整数都出现两次，你要找出这个只出现一次的整数。

比如说，给你的数组是：
5, 7, 5, 6, 6
这里 7 只出现了一次，因此你要返回的就是 7。

代码#

public class AlgoCasts {

  // Time: O(n), Space: O(1)
  public int singleNumberWithXOR(int[] nums) {
    int result = 0;
    for (int num: nums) result ^= num;
    return result;
  }

  // Time: O(n), Space: O(n)
  public int singleNumberWithSet(int[] nums) {
    Set<Integer> set = new HashSet<>();
    int sum = 0, uniqueSum = 0;
    for (int num: nums) {
      if (!set.contains(num)) {
        uniqueSum += num;
        set.add(num);
      }
      sum += num;
    }
    return 2 * uniqueSum - sum;
  }

}