hot100 136.只出现一次的数字

思路1.题目要求线性的时间复杂度和常量级的空间复杂度。2.如果用hash表来做那么空间复杂度将会达到O(n)不符合题意。3.如果用暴力破解法每次从数组中取一个数记为cur然后从剩下的数中查找如果找不到则cur即为要找的那个数。这种解法的时间复杂度是O(n^2)。4.如何降低暴力解法的时间复杂度想到了排序。把暴力解法的时间复杂度从O(n^2)降低到O(n)有两个突破点1暴力解法做了很多重复的工作。2要充分利用题目的已有信息。通过第一点目前没有想到思路。但是通过第二点可以找到突破口。由于除了某个元素只出现一次以外其余每个元素均出现两次因此可以用异或运算求解。方法一哈希表。复杂度分析1时间复杂度O(n)。2空间复杂度O(n)不符合题意。附代码class Solution { public int singleNumber(int[] nums) { MapInteger,Integer map new HashMap(); for(Integer i : nums){ Integer count map.get(i); // count统计nums[i]出现的次数 count count null ? 1 : count; // 如果哈希表中没有则置为1否则count 1 map.put(i,count); } for(Integer i : map.keySet()){ Integer count map.get(i); if(count 1){ return i; } } return -1; //未找到 } }方法二异或运算。复杂度分析1时间复杂度O(n)需要遍历整个数组一次。2空间复杂度O(1)只使用了一个额外的变量ans来存储结果。附代码class Solution { public int singleNumber(int[] nums) { // 异或运算的性质 // 1.相同为0不同为1 a ^ a 0 // 2.任何数与0异或等于它本身 a ^ 0 a // 3.异或满足交换律和结合律 int ans nums[0]; if(nums.length 1){ for(int i 1;i nums.length;i){ ans ans ^ nums[i]; // 对数组中的所有数字做异或XOR运算 } } return ans; // 返回最终的异或结果 } }