只出现一次的数字 III【LC260】
给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
思路
实现
class Solution { public int[] singleNumber(int[] nums) { int xor = 0; for (int num : nums){ xor ^= num; } // 找到第一位为1的位置 int bit1 = 0; for (int i = 30; i >= 0; i--){ if (((xor >> i) & 1) == 1){ bit1 = i; break; } } int a = 0, b = 0; for (int num : nums){ if (((num >> bit1) & 1) == 1){ a ^= num; }else{ b ^= num; } } return new int[]{a, b}; } }
复杂度
时间复杂度：O ( n )
空间复杂度：O ( 1 )
