Java教程

剑指 Offer 56 - I. 数组中数字出现的次数(位运算)

本文主要是介绍剑指 Offer 56 - I. 数组中数字出现的次数(位运算),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

剑指 Offer 56 - I. 数组中数字出现的次数

问题:一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

思路:136. 只出现一次的数字 即如果除了一个数字以外,其他数字都出现了两次,我们可以用异或求解出这个数字。这是求解一个出现一次的数字,而这道题有两个出现一次的数字需要求解。我们考虑将数组分为两组,且这两个出现一次的数字分别在一组,然后再使用异或的方法就可以求出这两个数字。具体如下:

假设这两个数字分别为a,b。将数组中所有元素异或后,得到的结果resa ^ b。此时考虑res的二进制位的意义,某一位为0,说明a和b这一位同为0或同为1。某一位为1,则表示a与b这一位不相等,即一个这一位为0,另一个这一位为1。根据这个不同位,也就是res某一位为1,将数组分组,肯定可以将a和b分开分到两组。res可能会有许多位为1的情况,我们只需要取某一位就行。可以选择最低位1的位置,假设是第i位。然后根据第i位将数组分组,对于数组中的每个元素来说,若第i位为1,分为一组,否则分为另一组,分组的同时分别对两组元素进行异或运算,最后得到的两个结果即为所求。

求解res最低位1的位置,

  • 官方题解给的方法是:令firstOne=1,然后与上res即res & firstOne。若为0,则firstOne左移一位,继续判断,直到找到为止。这里需要注意的是firstOne是一个只有一位为1的数,所以res & firstOne的结果有两种:0或firstOne。则while循环的判断条件不能是(res & firstOne) != 1。我第一次就是这样写的,结果发现有个示例超时了。
  • 还有一种评论里的求法,很巧妙:firstOne = res & (-res)。以18为例,-18的二进制表示就是18二进制表示的补码,也就是反码加1。18的二进制表示为1010。它的反码为0101,再加1为0110。则18 & (-18)1010 & 0110 = 0010。这样可以快速求得18最低位1的位置。
class Solution {
    public int[] singleNumbers(int[] nums) {
        int res = 0;
        for(int num: nums){
            res ^= num;
        }

        int firstOne = res & (-res);
        // while((res & firstOne) == 0){
        //     lastOne <<= 1;
        // }

        int a = 0, b = 0;
        for(int num: nums){
            if((firstOne & num) == 0){
                a ^= num;
            } else {
                b ^= num;
            }
        }
        return new int[]{a, b};
    }
}

整理思路,记录博客,以便复习。若有误,望指正~

这篇关于剑指 Offer 56 - I. 数组中数字出现的次数(位运算)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!