每日算法 只出现一次的数字

例题：136. 只出现一次的数字

题目描述：

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

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

本题思路：

暴力破解固然可以，代价就是慢慢慢。

利用好数字二进制的异或关系，便可以轻松地去进行筛选。

另外也可以用哈希表的方法进行数字出现次数的计算，以达到找到只出现一次的数字。但因为用了哈希表和双for循环，会导致运行时间变很久。

代码：

//暴力破解版
public class Solution {
    public int singleNumber(int[] nums) {
        // 遍历数组中的每个元素
        for (int i = 0; i < nums.length; i++) {
            int count = 0;
            // 再次遍历数组，统计当前元素出现的次数
            for (int j = 0; j < nums.length; j++) {
                if (nums[j] == nums[i]) {
                    count++;
                }
            }
            // 如果当前元素只出现了一次，则返回该元素
            if (count == 1) {
                return nums[i];
            }
        }
        // 如果没有找到只出现一次的元素，返回 -1 或者其他适当的值
        return -1;
    }
}

//二进制异或版
//普通for循环版本
class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            int temp = nums[i];
            result ^= temp;
        }
        return result;
    }
}

//for-each版本
class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int n:nums) {
            result ^= n;
        }
        return result;
    }
}
//两种方法的时间复杂度几乎相同，可能普通for循环版本因为多了一个给i和temp的赋值过程数据量大了会慢一些

//哈希表
class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (Integer i : nums) {
            Integer count = map.get(i);
            count = count == null ? 1 : ++count;
            map.put(i, count);
        }
        for (Integer i : map.keySet()) {
            Integer count = map.get(i);
            if (count == 1) {
                return i;
            }
        }
        return -1; // can't find it.
    }
}

哈希表解法详细：

先创建一个Hash表，通过第一个for-each循环将nums数组里面的值作为键值在每个循环内将对应键值的value挨个赋值给count。通过循环内 count = count == null ? 1 : ++count;给hash表中对应键值的value进行检测，也就是说nums数组中的值第一次进hash表时value为null，通过count = count == null ? 1 : ++count;进行赋值为1，当被count = count == null ? 1 : ++count;检测到nums数组中重复的值进入hash表中则对其对应的value进行++操作，达到计数的效果。

第二个循环遍历hash表中的key，然后通过 Integer count = map.get(i);去获取hash表中key对应的value，也就是对应值的计数值。之后当if判断检测到计数值为1时，即找到只出现一次的数。