只出现一次的数字
136. 只出现一次的数字
剑指 Offer II 004. 只出现一次的数字
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
示例 1：
输入：nums = [2,2,3,2]
输出：3
示例 2：
输入：nums = [0,1,0,1,0,1,100]
输出：100
提示：
1 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
注意：本题与主站 137 题相同：https://leetcode-cn.com/problems/single-number-ii/
题解
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; } }
260. 只出现一次的数字 III
260.只出现一次的数字 III
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
示例 1：
输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。
示例 2：
输入：nums = [-1,0]
输出：[-1,0]
示例 3：
输入：nums = [0,1]
输出：[1,0]
提示：
2 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
除两个只出现一次的整数外，nums 中的其他数字都出现两次
class Solution { public int[] singleNumber(int[] nums) { int xorsum = 0; for (int num : nums) { xorsum ^= num; } // 防止溢出 int lsb = (xorsum == Integer.MIN_VALUE ? xorsum : xorsum & (-xorsum)); int type1 = 0, type2 = 0; for (int num : nums) { if ((num & lsb) != 0) { type1 ^= num; } else { type2 ^= num; } } return new int[]{type1, type2}; } }
