东莞网站制作购买,建设玩外汇平台网站,小公司有必要买财务软件吗,盐城市建设银行网站一、题目 给你一个整数数组 nums#xff0c;其中恰好有两个元素只出现一次#xff0c;其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。 示例 1#xff1a;
… 一、题目 给你一个整数数组 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]二、思路解析 首先我们可以先做个小优化当 nums 数组长度为 2 时说明这两个元素一定只出现了一次直接返回即可。
然后就要利用到我们熟悉的两条公式 x ^ x 0 x ^ 0 x 由于数组中除了两个数字之外其他数字都出现了两次因此我们对数组中的所有数字进行异或运算得到的结果即为两个只出现一次的数字的异或结果。
在第三部分的代码中我用 n1 和 n2 表示这两个数。
再对数组使用一次 lowbit 运算目的是根据最低位的不同把这两个只出现一次的数字分到两个不同的组。
接着我们在遍历一次数组当有元素和 lowbit 进行或运算后还不等于零则他就是 n1 了。
另一个只出现一次的数就让 n1 和 Double 异或一下就出来了因为 Double 本身就是这两个数的异或。 三、完整代码 class Solution {public int[] singleNumber(int[] nums) {if(nums.length 2){return nums;}int Double 0;for(int i 0 ; i nums.length ; i ){Double ^ nums[i];}int n1 0;int lowbit Double -Double;for(int j 0 ; j nums.length ; j ){if((nums[j] lowbit) ! 0){n1 ^ nums[j];} }int n2 Double ^ n1;return new int[]{n1 , n2};}
} 以上就是本篇博客的全部内容啦如有不足之处还请各位指出期待能和各位一起进步
