网站结构布局,深圳品牌咨询公司,wordpress模板 户外钓鱼类网站,外网建筑设计网站文章目录题目描述思路 代码题目描述
比 leetcode 136要难点注意#xff1a;空间复杂度要求O(1)#xff0c;否则用哈希表直接秒杀啦。昨天的笔试#xff0c;还有刷的面经都有这道题。。。今天赶紧补补
思路 代码
相对于 leetcode 136#xff0c;这边多了个分…
文章目录题目描述思路 代码题目描述
比 leetcode 136要难点注意空间复杂度要求O(1)否则用哈希表直接秒杀啦。昨天的笔试还有刷的面经都有这道题。。。今天赶紧补补
思路 代码
相对于 leetcode 136这边多了个分组的考点相当于分成两个 leetcode 136如何分组用整组异或结果找到第一个 1 位作为location也就是两个答案的第一个不同位以这个location作为标准把数组分成两个子数组此位为1的数此为为0的数可证两个子数组一定都满足“数组中有一个数出现了一次其他数都出现了两次”证明首先location本就是把两答案区分开的那么如何证明子数组中的其他数都是成对的呢这个简单就是因为原数组本就是成对的用location作为标准也是把元素成对区分到子数组中。
class Solution {public int[] singleNumbers(int[] nums) {// 1. 取异或值int XOR 0;for(int i : nums){XOR ^ i;}// 2. 找到第一个为 1 的位int location 1;while((XOR location) 0){location 1;}// 3. 在两个子数组中找到两个答案int ans1 0;int ans2 0;for(int i : nums){if((i location) ! 0){ans1 ^ i;}else{ans2 ^ i;}}return new int[]{ans1, ans2};}
}无注释版
class Solution {public int[] singleNumbers(int[] nums) {int xor 0;for(int temp : nums) {xor ^ temp;}int firstOne 1;while((xor firstOne) 0) {firstOne 1;}int ans1 0, ans2 0;for(int temp : nums) {if((temp firstOne) 0) {ans1 ^ temp;}else {ans2 ^ temp;}}return new int[]{ans1, ans2};}
}
