剑指 Offer II 004. 只出现一次的数字 - 力扣（LeetCode） (leetcode-cn.com)https://leetcode-cn.com/problems/WGki4K/
想直接通过数组遍历的暴力破解，但是在用例[43,16,45,89,45,-2147483648,45,2147483646,-2147483647,-2147483648,43,2147483647,-2147483646,-2147483648,89,-2147483646,89,-2147483646,-2147483647,2147483646,-2147483647,16,16,2147483646,43]
的情况下，会导致数组访问越界。
class Solution { public int singleNumber(int[] nums) { int result=-1; //findMax int max=nums[0]; int min=nums[0]; for(int i=1;i<nums.length;i++){ if(max<nums[i]){ max=nums[i]; } if(min>nums[i]){ min=nums[i]; } } if(min<0){ for(int i=0;i<nums.length;i++){ nums[i]-=min; } max-=min; } //初始化 int []array=new int[max+1]; for(int i=0;i<array.length;i++){ array[i]=-1; } for(int i=0;i<nums.length;i++){ array[nums[i]]+=1; } for(int i=0;i<array.length;i++){ if(array[i]==0){ result=i; } } if(min<0){ result+=min; } return result; } }反思：位运算掌握较差，总是忽略边界值的验证。
换思路，利用题目条件，相同数字必出现三次。
class Solution {
public int singleNumber(int[] nums) {
int result=-1;
Arrays.sort(nums);
for(int i=0;i<nums.length;i++){
System.out.println(nums[i]);
}
if(nums.length==1){
result=nums[0];
}else{
for(int i=0;i<nums.length-1;i+=3){
if(nums[i]!=nums[i+1]){
result=nums[i];
System.out.println("result="+nums[i]);
break;
}
}
if(nums[nums.length-1]!=nums[nums.length-2]){
result=nums[nums.length-1];
}
}
return result;
}
}
麻了，复杂度也太差了。
康康官方解题。
方法一：哈希表
思路与算法我们可以使用哈希映射统计数组中每个元素的出现次数。对于哈希映射中的每个键值对，键表示一个元素，值表示其出现的次数。
在统计完成后，我们遍历哈希映射即可找出只出现一次的元素。
class Solution { public int singleNumber(int[] nums) { Map<Integer, Integer> freq = new HashMap<Integer, Integer>(); for (int num : nums) { freq.put(num, freq.getOrDefault(num, 0) + 1); } int ans = 0; for (Map.Entry<Integer, Integer> entry : freq.entrySet()) { int num = entry.getKey(), occ = entry.getValue(); if (occ == 1) { ans = num; break; } } return ans; } } 作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/WGki4K/solution/zhi-chu-xian-yi-ci-de-shu-zi-by-leetcode-0vrt/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。复杂度分析
时间复杂度：O(n)，其中 nn 是数组的长度。
空间复杂度：O(n)。哈希映射中包含最多 ⌊n/3⌋+1 个元素，即需要的空间为 O(n)。
方法二：依次确定每一个二进制位
思路与算法为了方便叙述，我们称「只出现了一次的元素」为「答案」。
由于数组中的元素都在 \texttt{int}int（即 3232 位整数）范围内，因此我们可以依次计算答案的每一个二进制位是 00 还是 11。
具体地，考虑答案的第 ii 个二进制位（ii 从 00 开始编号），它可能为 00 或 11。对于数组中非答案的元素，每一个元素都出现了 33 次，对应着第 ii 个二进制位的 33 个 00 或 33 个 11，无论是哪一种情况，它们的和都是 33 的倍数（即和为 00 或 33）。因此：
答案的第 ii 个二进制位就是数组中所有元素的第 ii 个二进制位之和除以 33 的余数。
这样一来，对于数组中的每一个元素 xx，我们使用位运算 \texttt{(x >> i) \& 1}(x >> i) & 1 得到 xx 的第 ii 个二进制位，并将它们相加再对 33 取余，得到的结果一定为 00 或 11，即为答案的第 ii 个二进制位。
细节
需要注意的是，如果使用的语言对「有符号整数类型」和「无符号整数类型」没有区分，那么可能会得到错误的答案。这是因为「有符号整数类型」（即 \texttt{int}int 类型）的第 3131 个二进制位（即最高位）是补码意义下的符号位，对应着 -2^{31}−2
31
，而「无符号整数类型」由于没有符号，第 3131 个二进制位对应着 2^{31}2
31
。因此在某些语言（例如 \texttt{Python}Python）中需要对最高位进行特殊判断。class Solution { public int singleNumber(int[] nums) { int ans = 0; for (int i = 0; i < 32; ++i) { int total = 0; for (int num: nums) { total += ((num >> i) & 1); } if (total % 3 != 0) { ans |= (1 << i); } } return ans; } } 作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/WGki4K/solution/zhi-chu-xian-yi-ci-de-shu-zi-by-leetcode-0vrt/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。复杂度分析
时间复杂度：O(nlogC)，其中 nn 是数组的长度，CC 是元素的数据范围，在本题中 \log C=\log 2^{32} = 32logC=log2
32
=32，也就是我们需要遍历第 0\sim310∼31 个二进制位。空间复杂度：O(1)。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/WGki4K/solution/zhi-chu-xian-yi-ci-de-shu-zi-by-leetcode-0vrt/
来源：力扣（LeetCode）