异或什么意思
异或什么意思
异或什么意思异或特征
异或(^): 相同为0,不同为1
N ^ 0 = N
N ^ N = 0
符合交换律和结合律: a^b=b^a (a^b)^c=a^(b^c)
两数交换:
a=a^b;b=a^b;a=a^b;
只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
使用异或运算,将所有值进行异或异或运算,相异为真,相同为假,所以 a^a = 0 ;0^a = a因为异或运算 满足交换律 a^b^a = a^a^b = b 所以数组经过异或运算,单独的值就剩下了
package array;/** * @author Darling yu * @version 1.0 * @date 2022/9/12 18:03 * 只出现一次的数字:给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗? */public class SingleNumber { public static void main(String[] args) { int[] nums = {4,1,2,1,2}; Solution solution = new Solution(); System.out.println(solution.singleNumber(nums)); } static class Solution { /*** 使用异或运算,将所有值进行异或* 异或运算,相异为真,相同为假,所以 a^a = 0 ;0^a = a* 因为异或运算 满足交换律 a^b^a = a^a^b = b 所以数组经过异或运算,单独的值就剩下了* @param nums* @return*/ public int singleNumber(int[] nums) {int reduce = 0;for (int num : nums) { reduce = reduce ^ num;}return reduce; } }}
出现奇数次的两个数字
只有两种数出现奇数次,其他的数都出现偶数次,找出出现奇数次的这两个数
package array;/** * @author Darling yu * @version 1.0 * @date 2022/9/12 18:03 * 出现奇数次的两个数字:给定一个非空整数数组,只有两种数出现奇数次,其他的数都出现偶数次,找出出现奇数次的这两个数。 * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗? */public class SingleNumberII { public static void main(String[] args) { int[] nums = {1, 1, 1, 2, 2, 3, 3, 3, 4, 4}; Solution solution = new Solution(); solution.singleNumberII(nums); } static class Solution { /*** 假设出现奇数次的两个数是a和b* 将所有数进行异或,最终得到的reduce=a^b* 因为a b是不同的两个数,reduce!=0,那么reduce必定有一位上面是1,* 也就是a,b两个数至少在某一位上面,一个数是1,另一个是0* 通过对reduce取反加一,再对自己进行&运算,得到最右侧的1的位置* 说明a b在这个位置上一个数是1 另一个是0* 将数组中的每个数与该位置1进行&运算,如果等于0,那这些数中必定有a或者b,假设为a* 这些数进行异或之后,剩下的就是a* 再与reduce异或,a^reduce=a^a^b=b得到另一个数b** @param nums* @return*/ public void singleNumberII(int[] nums) {int reduce = 0;// 将所有数进行异或 最终得到的reduce=a^bfor (int num : nums) { reduce = reduce ^ num;}// reduce有一个位置上是1// 假设reduce= 1001100// ~reduce取反= 0110011// ~reduce+1=0110100// reduce & (~reduce+1)= 0000100int rightOne = reduce & (~reduce + 1); // 提取出最右侧的1int onlyOne = 0;for (int num : nums) { //(num & rightOne) == 0 或者(num & rightOne) == rightOne if ((num & rightOne) == 0) {// 说明num在reduce最右侧的1的位置上是0 onlyOne ^= num; }}System.out.println("一个数是:" + onlyOne);System.out.println("另一个数是:" + (onlyOne ^ reduce)); } }}
-
- 什么是利率(什么是利率互换)
-
2023-05-25 17:53:41
-
- 选车位柱子靠左还是右
-
2023-05-25 15:24:17
-
- 香肠是煮熟还是蒸熟
-
2023-05-25 15:22:11
-
- 线上是什么意思?
-
2023-05-25 15:20:05
-
- 戊午是几点
-
2023-05-25 15:17:59
-
- 微信运动怎么关闭
-
2023-05-25 15:15:53
-
- 天能号和和谐号区别
-
2023-05-25 15:13:47
-
- 手机死机屏幕一直亮着
-
2023-05-25 15:11:41
-
- 生日蛋糕可以放冰箱几天
-
2023-05-25 15:09:35
-
- 陕北是指哪些地方
-
2023-05-25 15:07:29
-
- 三清三关是指
-
2023-05-25 15:05:23
-
- kksk什么意思(kksk什么意思网络用语)
-
2023-05-25 10:40:32
-
- allin是什么意思(英雄联盟allin是什么意思)
-
2023-05-25 10:38:27
-
- 孕妇吃葡萄对胎儿有什么好处(怀孕期间吃葡萄对胎儿有什么好处)
-
2023-05-25 10:36:22
-
- 什么是科普
-
2023-05-25 10:34:17
-
- 专科什么意思
-
2023-05-25 10:32:12
-
- 四川有什么市(四川一共有多少个市)
-
2023-05-25 10:30:07
-
- 基本图形(基本图形是什么意思)
-
2023-05-25 10:28:03
-
- 睡觉多梦是什么原因(睡觉多梦是什么原因怎样缓解)
-
2023-05-25 10:25:58
-
- sku是什么意思
-
2023-05-25 10:23:53