Problem:
1-这个数放在含有个元素的数组中,只有唯一的一个元素值重复，其他均只出现一次。设计一个算法，将它找出来，你能否设计一个算法实现?
思路1(最先想到的):
首先也是最暴力的方法就是一个循环嵌套一个循环,一个一个去找
时间复杂度为O(n)
下面是实现的代码:
思路2:
另外开辟一个大小为的数组arr，遍历原来的数组，原来数组中的数就是arr中的下标，若遇到一个数就将对应arr的下标位置对应的值加一就行。然后遍历arr数组，若遇到下标位置对应的值为2的时候,输出下标就行
时间复杂度为O(n)
下面是实现的代码:
思路3:
使用异或来找出唯一成对的数,这种算法的效率应该是最高的了,而且不需要辅助空间
先来说一下异或的规则:
a^a=0
a^0=a
然后我们的思路是将这个数全部异或起来,那么就会把相同的数给变成0了，那么怎么办呢?
我们可以再次将该数与1-之间的数给异或起来
那么不重复的数都会变成0，而重复的数不会变成0
时间复杂度为O(n)
下面是实现的代码: