网上服装商城网站建设方案策划,媒体这些渠道进行采集的是,去哪优化网站关键词,微信看视频打赏网站建设java数据结构与算法刷题目录#xff08;剑指Offer、LeetCode、ACM#xff09;-----主目录-----持续更新(进不去说明我没写完)#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 与运算取末尾1分组 与运算取末尾1分组
解题思路#xff1a;时间…java数据结构与算法刷题目录剑指Offer、LeetCode、ACM-----主目录-----持续更新(进不去说明我没写完)https://blog.csdn.net/grd_java/article/details/123063846 文章目录 与运算取末尾1分组 与运算取末尾1分组
解题思路时间复杂度O( n n n)空间复杂度O( 1 1 1) 数组中有两个元素a和b出现1次剩余都出现2次通过异或操作将出现2次的都抵消掉获得两个出现一次的数的异或结果a^b我们知道a^b的结果是两者二进制中值不同的位 1相同的 0.我们拿到a^b的最右边一个1也就是a和b最右边的不相同的一位rightOne。也就是说rightOne位置a的二进制和b的二进制不同一个1一个0 获取a的二进制最右边的1的经典操作办法是 rightOne a (-a).如果不懂可以参考下面文章中与运算的讲解 位运算https://blog.csdn.net/grd_java/article/details/136119268 既然我们拿到了rightOne。他的二进制形式是整个二进制串只有一个1例如0000010000,而这个1的位置是区分a和b的关键因为a和b中只有一个在rightOne的位置是1.而另一个一定是0. 因为a^b后1的位置代表a和b不同的位置这样我们将整个数组分成两组在rightOne位置为1的和在rightOne位置为0的然后我们对在rightOne位置为1的所有数字进行异或统计。其中出现两次的数字二进制不会有什么改变在rightOne位置的二进制都一样。所以异或过程中依然会抵消掉。最终结果会剩下出现一次的数字。a和b的一员。这里假设为a。 因为a和b只有一个在rightOne位置是1这里假设a在rightOne位置是1.而a只出现1次其它在rightOne位置是1的数都出现两次。异或后都会抵消。最终只剩下a 这样我们就找到了一个出现一次的数字a。然后我们还有a^b的结果我们将a^b^a (a^a)^b 0^b b.这样就找到了a和b。返回即可。 代码 class Solution {public int[] singleNumber(int[] nums) {int eor1 0;//对所有数进行异或最后将剩下两个只出现一次的数for (int num : nums) eor1 ^ num;//两数相同异或为0不同异或为1// eor1 : a ^ ba和b的二进制位如果不同结果就是1// 正负相与保留最末尾的1int RightOne eor1 (-eor1);//提取最右侧的1表示a和b二进制中最右侧第一个两者不一样的一位也就是这一位二进制a和b不一样。一个在这一位是1一个在这一位是0int eor2 0;//分组保存所有在这一位是0的数的异或结果。而另一组在这一位是1的异或结果我们可以不做统计for (int num : nums) {//遍历所有数if ((num RightOne) 0) {//如果num在这一位是0,而RightOne在这一位肯定是1相与的结果必然是0而其它位rightOne都是0所以最终整个二进制结果一定是0eor2 ^ num;//将其进行异或最终出现两次的都会抵消而一定会遇上a和b中这一位是0的那个,假设是a然后eor2 a}}return new int[] { eor2, eor1 ^ eor2 };//eor1 a^b 假设eor2 a.则eor1 ^ eor2 a ^ b ^ a b }
}
