因此这种方法的时间复杂度非常高,程序的运行效率很低.
进阶思路:
在C语言中有一个异或(^)逻辑运算符,我们可以利用它的自反性质来找出"单身狗"....【C语言】异或(^)操作符详解
先将文章里面的部分内容截出方便我们后续使用:
异或的运算法则(部分):
接下来我们画图来解释一下异或操作的步骤:
可以发现,凡是出现过两次的数字,两两异或后都变成了0,而唯一的只出现了一次的数字...:
可以看到,该代码同样成功得到了我们想要的结果,并且当数组中有n个元素时,代码循环的次数为n,比常规思路中的n^n的时间复杂度简化了不少,运行效率也非常高....,有数字找到了和它相同的数字,那么终止循环,换下一个数字遍历,
直到找出遍历完整个数组都没有找到与它相同的数,将这个数打印/存储,
再继续换下一个数遍历,寻找下一个"单身狗"....它们的二进制末位都是0时,该如何将它俩区分呢?
这时我们可以尝试将两个单身狗异或一下,就能找到其中的规律.