南京秦淮区建设局网站,wordpress深入理解,中国广电山东网络有限公司,wordpress类开源网站文章目录 异或运算的概念异或运算的性质交换两个变量的值#xff08;不使用额外变量#xff09;只出现一次的数字只出现一次的数字 III只出现一次的数字 II 异或运算的概念
对应二进制位进行异或运算对应二进制位上#xff0c;相同结果为0#xff0c;不同结果为1
小技巧不使用额外变量只出现一次的数字只出现一次的数字 III只出现一次的数字 II 异或运算的概念
对应二进制位进行异或运算对应二进制位上相同结果为0不同结果为1
小技巧异或运算可以记为无进位相加 现在有两个整数 A A A和 B B B A A A 等于7 B B B等于13那么 A A A^ B B B怎么运算呢
// 十进制 A 7 B 13
// 二级制
// A: 0111
// B: 1101
// --------
// 1010A A A ^ B ( 1010 ) 2 ( 10 ) 10 B (1010)_2 (10)_{10} B(1010)2(10)10
异或运算的性质
满足交换律 A A A ^ B B B B B B ^ A A A证明: A A A和 B B B无进位相加等于 B B B和 A A A无进位相加 满足结合律 ( A (A (A ^ B ) B) B) ^ C C C A A A ^ ( B (B (B^ C ) C) C)证明 A A A和 B B B无进位相加在和 C C C无进位相加等于 B B B和 C C C无进位相加在和 A A A无进位相加 * 0 0 0 ^ N N N N N N 证明 0 0 0和 N N N无进位相加结果还是 N N N N N N ^ N N N 0 0 0 证明 N N N和 N N N无进位相加结果为 0 0 0 请理解并记住这里的性质后面会使用到。
交换两个变量的值不使用额外变量 这是一个经典的面试题,代码如下请读者先自行理解。
public class Test {// 交换数组中 i 和 j 两个位置的值注意i j如果i j 那么 arr[i] arr[j]// 那么经过异或运算N ^ N 0后会把arr[i] arr[j]位置的值刷成0public static void swap(int[] arr,int i,int j) {arr[i] ^ arr[j];arr[j] ^ arr[i];arr[i] ^ arr[j];}public static void main(String[] args) {int a 3;int b 5;// swap1a a ^ b; // ①b a ^ b; // ②a a ^ b; // ③System.out.println(a b);}
}为什么跑完①②③就能完成两个变量的交换呢现在我们将 a a a记作 a 1 a_1 a1,b记作 b 1 b_1 b1第一步 a a 1 a a_1 aa1 ^ b 1 b_1 b1第二部 b ( a 1 b (a_1 b(a1 ^ b 1 ) b_1) b1) ^ b 1 a 1 a b_1 a_1 a b1a1a第三步 a ( a 1 a (a_1 a(a1 ^ b 1 ) b_1) b1)^ a 1 b 1 a_1 b_1 a1b1在这里进行计算式不要忽视了上一步计算的对 a b a b ab的影响。这样跑完这三行代码之后就玩成了对两个变量的交换。注意位运算的效率远高于算术运算。
只出现一次的数字 这是一道leetcode原题传送门请点我!!! 给你一个 非空 整数数组 nums 除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间。 那么怎么考虑这个问题呢我们前面讲过异或运算满足交换律和结合律那么在这里设这组数为 n u m s 1 , n u m s 2 , n u m s 3 , . . . . . . n u m s n − 1 nums_1,nums_2,nums_3,...... nums_{n - 1} nums1,nums2,nums3,......numsn−1 假设 n u m s i nums_i numsi 为数组中出现了奇数次的数我们队这组数调整顺序 n u m s i , n u m s 1 , n u m s 2 , . . . . . . n u m s i , n u m s i 1 , . . . . . . n u m s n − 1 nums_i, nums_1 , nums_2, ...... nums_{i}, nums_{i 1},......nums_{n-1} numsi,nums1,nums2,......numsi,numsi1,......numsn−1 调整完顺序之后由于除了 n u m s i nums_i numsi其他数都出现了偶数次那么有 n u m s i nums_i numsi ^ n u m s 1 nums_1 nums1 ^ n u m s 2 nums_2 nums2 ^ … ^ n u m s n − 1 n u m s i nums_{n - 1} nums_i numsn−1numsi ^ 0 n u m s i 0 nums_i 0numsi 有了上述推导我们只要将所有数全部都异或到初值为 0 0 0的变量 x o r xor xor中就可以在 O N ON ON的时间复杂度 O ( 1 ) O(1) O(1)的空间复杂度内得到出现了奇数次的数了。 public static void oddTimesNum(int[] arr) {int xor 0;for (int num : arr) {// foreach迭代器实现xor ^ num;}System.out.println(xor);}只出现一次的数字 III 这是一道leetcode原题传送门清点我!!! 给你一个整数数组 nums其中恰好有两个元素只出现一次其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。 我们首先强化一下这个命题有两个元素出现了奇数次其他元素都出现了偶数次找出那两个出现奇数次的数。 在介绍这道题之前我们先介绍一种操作就是提取出一个数二进制中最右侧的1比如提取出24最右侧的1
// 24
// 11000
// 提取出最右侧的1
// 01000 8那么怎么完成这个操作呢 a a a ( a 1 ) (~a 1) ( a1) 就能做到这个操作。
// 就拿a 24举例
// a 11000
// ~a 00111 //~a1 01000
// a 11000
// ------------
// 01000
// 这样就取出了a最右侧的1有了上面的铺垫我们就可以继续看这道题目了我们先将所有数异或到初值为 0 0 0的变量 x o r 1 xor1 xor1中 x o r 1 n u m s 1 xor1 nums_1 xor1nums1 ^ n u m s 2 nums_2 nums2 ^ … ^ n u m s n − 1 nums_{n - 1} numsn−1 设这两个奇数为 a a a b b b那么有 x o r 1 a xor1 a xor1a ^ b b b 我们继续分析我们可以 x o r 1 xor1 xor1中最右侧的1提取出来由于a ! b ! b !b所以 x o r 1 xor1 xor1的二进制位中一定会有 1 1 1比如 x o r 1 xor1 xor1的第 i i i位为 1 1 1。那么这意味这什么意味着a和b的二进制在第i位上是不一样的这样我们就可以用这个性质将数组中的数分为两类一类是第 i i i位是 1 1 1的一类是第 i i i位是 0 0 0的。我们在准备一个初值为 0 0 0的变量 x o r 2 xor2 xor2将第一类数全部异或上。我们分析下异或后 x o r 2 xor2 xor2的值。 x o r 2 a xor2 a xor2a ^ . . . . . . ...... ...... 后面可能有数可能没数这不影响因为它们会出现偶数次异或后值为0 我们发现 x o r 2 xor2 xor2的值为 a a a最后我们只需要将 x o r 2 xor2 xor2和 x o r 1 xor1 xor1异或就可以得到另一个数 b b b了!!! public static void printOddTimesNum2(int[] arr) {// 两种数 一种为 a 一种为 bint xor1 0;for (int num : arr) {xor1 ^ num;}// 此时 eor1 a ^ b;// 数组中所有的数可以分为两类(a ! b)// 拿到eor最右侧的1 eor (~eor 1) (eor (-eor))// 1. 第一类rightOne a 和一些出现了偶数次的数// 2. 第二类NonRightOne b 和一些出现了偶数次的数int rightOne xor1(~xor1 1);int xor2 0;for(int num : arr) {if((num rightOne) ! 0) {xor2 ^ num;}}// 此时eor1就得到了第一类数,再将xor1和xor2进行异或就可以得到第二类数了System.out.println(xor2 (xor1 ^ xor2));}只出现一次的数字 II 这是一道leetcode原题传送门清点我!!! 给你一个整数数组 nums 除某个元素仅出现 一次外其余每个元素都恰出现三次 。请你找出并返回那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。 同样我们先强化一下这个命题数组nums中某个元素出现了k次其余每个元素都出现了 m m m次找到并返回出现了 k k k次的数。那么对于这个问题我们又该如何取作呢 这个问题我们是这样考虑的先准备一个长度为32的二进制信息数组t将nums数组中的所有数的二进制中 1 1 1出现的次数统计到t数组中。由于 k m k m km所以对于t数组中的每一位如果t[i]的值是对m取余等于k说明出现了k次的数的二进制在第 i i i位上是 1 1 1。什么意思举个例子当 k 1 m 3 k 1 m 3 k1m3 是就是上面这道leetcode原题给定nums数组[2,2,3,2]我们统计其中所有数的二进制信息得到t数组 [00000000 00000000 00000000 00000041]其中第32位为1对 m m m3取模后等于k所以出现 k k k次的数在第32位上是1同理第31位上也是1最后得到出现 k k k次的数字的二进制0011从而还原出3出现了 k k k次。 我们还可以讨论组成第 t [ i ] t[i] t[i]位的数值的情况可能出现了 k k k次的数在这位上是 1 1 1可能其他出现了 m m m次的数在这位上也是 1 1 1。
① t [ i ] k n × m ( n t[i] k n \times m(n t[i]kn×m(n个数出现了 m m m次 n n n n u m s . l e n g t h − k m nums.length - k \over m mnums.length−k),我们可以让 t [ i ] t[i] t[i] 对m取模如果等于 k k k则出现了 k k k次的数在第 i i i位上是 1 1 1。
② t [ i ] k t[i] k t[i]k,由于 k m k m km 所以对 m m m取模值还是 k k k k kk所以现了 k k k次的数在第i位上是 1 1 1。
③ t [ i ] n × m t[i] n \times m t[i]n×m,对 m m m取模后值为 0 0 0所以现了 k k k次的数在第 i i i位上是 0 0 0。
④ t [ i ] 0 ! k t[i] 0 ! k t[i]0!k,所以现了 k k k次的数在第 i i i位上是 0 0 0。 综上只要满足 t [ i ] t[i] t[i] % m k m k mk则出现了看次的数在第i位上是 1 1 1从而还原出出现了 k k k次的数。
public static int OnlyKTimes(int[] arr, int k, int m) {int[] t new int[32];for (int x : arr) {// foreachfor (int i 0; i 31; i) {t[i] (x i) 1;// ①统计位1}}int ans 0;for (int i 0; i 31; i)if (t[i] % m 0k) {ans | (1 i);// ②设置答案}return ans;
}这里留下①和②两个点读者可以自行思考。
