四川平昌县建设局网站,华强北做电子网站,网站建设活动,游戏创业项目给你一个整数数组 nums#xff0c;其中恰好有两个元素只出现一次#xff0c;其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
示例 1#xff1a;
输入其中恰好有两个元素只出现一次其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
示例 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 中的其他数字都出现两次
题解 位运算
将 x 的所有位都取反得到的值。通过与原数 x 进行按位与运算可以得到一个结果其中只有最低位的 1 保留下来其他位都为 0。
这个方法的原理在于当对一个数 x 取反时得到的 -x 在二进制表示上是 x 的按位取反加 1。因此-x 的二进制表示中最低位的 1 对应的位置就是 x 中最低位的 1 的位置。通过与 x 进行按位与运算可以将这个最低位的 1 提取出来。code: 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};}
