异或运算非独立思考

    1. class Solution {
    2.     public int singleNumber(int[] nums) {
    3.         // 思路1：使用哈希表存储每个数字和该数字出现的次数。
    4.         // 遍历数组即可得到每个数字出现的次数，并更新哈希表，最后遍历哈希表，得到只出现一次的数字。
    5.         // 思路2：使用集合存储数字。这里集合可以使用List
    6.         // 遍历数组中的每个数字，如果集合中没有该数字，则将该数字加入集合，如果集合中已经有该数字，则将该数字从集合中删除，最后剩下的数字就是只出现一次的数字。
    7.         // 但是以上方法时间复杂度均为O(N)
    8.         // 答案，使用异或运算：任何数和其自身做异或运算，结果是 0
    9.         // 又因为异或运算满足交换律
    10.         int sum = 0;
    11.         for (int num : nums) {
    12.             sum ^= num;
    13.         }
    14.         return sum;
    15. //        HashMap<Integer, Integer> map = new HashMap(16);
    16. //        for (int i = 0; i < nums.length; i++) {
    17. //            if (map.containsKey(nums[i])) {
    18. //                map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
    19. //            } else {
    20. //                map.put(nums[i], 1);
    21. //            }
    22. //        }
    23. //        for (Integer key : map.keySet()) {
    24. //            if (map.get(key) == 1) {
    25. //                return key;
    26. //            }
    27. //        }
    28. //        return 0;
    29.     }
    30. }
    1. class Solution {
    2.     public int singleNumber(int[] nums) {
    3.         HashMap<Integer,Integer> map = new HashMap<>();
    4.         for (Integer num : nums) {
    5.             if (map.get(num)!=null){
    6.                 map.remove(num);
    7.             }else {
    8.                 map.put(num,1);
    9.             }
    10.         }
    11.         return map.keySet().iterator().next();
    12.     }
    13. }
    1. class Solution {
    2.     public int singleNumber(int[] nums) {
    3.         HashSet<Integer> set = new HashSet<>();
    4.         int arraySum = 0;
    5.         int setSum = 0;
    6.         for (int num : nums) {
    7.             set.add(num);
    8.             arraySum += num;
    9.         }
    10.         for (Integer integer : set) {
    11.             setSum += integer;
    12.         }
    13.         return setSum * 2 - arraySum;
    14.     }
    15. }