异或 ^ ,进行二进制位运算,相同则返回0,不同则返回1。
如果快速寻找一个数组中仅出现过一次的元素,例如输入{2,2,1},返回1,输入{1,2,3,4,5,6,5,3,4,2,1},返回6。要求时间复杂度为O(n)而且不能使用额外空间。
利用异或位运算的性质:A^0 = A , A^A = 0,因而只需要对所有元素进行一次异或运算即可。
代码如下:
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23using System; namespace ConsoleApp4 { public class Solution { static void Main() { int[] a = { 1,2,3,4,5,6,5,3,2,1,6}; Console.WriteLine( func(a)); } static int func(int[] a) { int ret = 0; for (int i = 0; i < a.Length; i++) { ret = ret ^ a[i]; } return ret; } } }
返回值为4。
同时,异或运算也可以用来交换元素,例如元素a,b,通过 a = a^b, b = a^b , a = a^b 这三步即可完成交换,不需要temp临时变量。
最后
以上就是平淡银耳汤最近收集整理的关于异或运算——快速寻找一个数组中仅出现一次的元素的全部内容,更多相关异或运算——快速寻找一个数组中仅出现一次内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复