关于算法:算法笔记二出现基数次的数字

5次阅读

共计 1994 个字符，预计需要花费 5 分钟才能阅读完成。

在左程云左神的算法课上，有这样一道例题：已知数组 int[] arr :
Q1：在 arr 中，只有一种数呈现了奇数次，其余数均呈现偶数次，请找出这个呈现了奇数次的数。Q2：在 arr 中，有两种数呈现了奇数次，其余数均呈现偶数次，请找出这两个呈现了奇数次的数。例：int[] {2,2,3,3,4,4,5,5,5},5 呈现了 3 次，奇数次。其余数字均呈现两次，偶数次。

异或运算：按位运算，如果 a、b 两个值不雷同，则异或后果为 1。如果 a、b 两个值雷同，异或后果为 0。符号 xor，记作 ^。例：a=00101011b,b=10110100b,a^b=10010001b
** 性质：**
1. 归零率：a^a=0;
2. 恒等率：a^0=a;
3. 交换律：a^b=b^a;
4. 结合律：a^b^c=(a^b)^c=a^(b^c);
5. 自反：a^b^a=b;

利用异或运算的性质 1 归零率，偶数次呈现的数顺次纳闷，后果为 0。奇数次呈现的数顺次异或，后果为数自身。再依据性质 2 恒等率，一个数异或 0 则等于其自身。这样将数组里所有的数顺次异或，失去的后果则是呈现了基数次的那个数。

public static void PointOddTimesNumQ1Func(int[] arr){
        int eor = 0;
        for (int cur : arr) {eor^=cur;}
         System.out.println(“呈现基数次的数为：”+eor);
    }

假如 a 呈现了奇数次，b 呈现了奇数次，首先表明 a≠b，所以 a^b 不等于 0。由此可得，a 与 b 的二进制数，必然存在某一位不雷同。第一步：咱们首先，将数组内的所有元素顺次异或，依据异或运算的性质，得 int[] arr 顺次异或的后果 =a^b; 咱们记作 eor=a^b;

第二步，找到 a 与 b 的二进制数不雷同的最低位
例：a = 10001000b，b=0110000b，a 与 b 的第三位不同，则这一位的异或后果为 1，咱们去尝试找到这一位。eor=a^b=11101000，则最低位 =eor&(~eor+1)=00001000b，咱们记作 rightBit，咱们可失去，a 与 b 的二进制的第 3 位必定是不雷同的。第三步：遍历整个数组，每一个数字与 rightBit 进行与运算（cur&rightBit），如果失去的后果为 0，则示意，有可能这个数为 a / b 其中的一个，然而如果是 a，则示意 a 的二进制在第 3 位必定为 0，则 b 的第 3 位必定为 1。这样咱们就能将 a 和 b 划分分明界线。或者用 cur&rightBit==rightBit 判断，这样筛选进去的所有数，都是第 3 位为 1 的数，因为 a 和 b 是绝对独立的，则非 a 即 b。第四步，将第三步筛选进去的所有数进行顺次异或运算。因为其余数都是偶数次呈现，所以不论筛选进去其余数第三位是什么，他们本身异或的后果都是 0。这样就相当于，对 a 或者 b 做了一次独立异或。异或的后果则是 a 或 b，这样就找出了 a /b。eor=a^b, 咱们用 a / b 其中的一个，去异或 eor，则失去另外一个数。

留神：第三四步的核心思想，其实是怎么将 a 和 b 这两个呈现了奇数次的数字进行宰割。

public static void PointOddTimesNumQ2Func(int[] arr) {
        int eor = 0;
        for (int cur : arr) {eor^=cur;}
        int rightBit =0;
        rightBit = eor & (~eor+1);
        int eorAnother=0;
        for (int cur : arr) {if ((cur&rightBit)==rightBit)
                eorAnother^=cur;
        }
        System.out.println(eorAnother +"and"+ (eorAnother^eor));
    }

测试数组：new int[]{1,1,2,2,50,50,50,60,60,60}

以上为 (cur&rightBit)==rightBit 去宰割 a 和 b，测试后果为：

依照(cur&rightBit)== 0 条件去宰割 a 和 b，测试后果为：

这两个后果只是，计算出来的先后顺序不同，区别在乎你用什么样的条件，先去找出那个不同位为 0 的还是为 1 的。

例：a^b≠0，找出 a 和 b 二进制数的不雷同的最低位。办法为 eor=a^b,eor&(~eor+1)

能够看到，a 和 b 的二进制，在第 4 位开始不同。

这里自己斗胆提一句：过后在听左老师的课程时，左老师讲的是(cur&rightBit)== 0 和(cur&rightBit)== 1 是两个对抗的条件，自己过后没听懂，通过 Debug 发现，这里左老师说错了，0 应该和 rightBit 是对抗条件，别离找进去，不同位次为 1 或 0 的数字。如果大家对这一点有疑难的话，倡议本人 Debug，会解答你本人的纳闷，或者评论区一起探讨。

算法真的太美了，心愿大家都能坚持下去!!!!!!

正文完