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