大四时候的一个面试题，当时没想出来，给大家分享一下

题目大意：
有这样一个数组，除其中一个元素（如下面的99），其它的都是成对出现的，如何能快速找出那99的位置
……102，102，2，2，44，44，99，23，23，11，11 …… 

106 个解决方案

#1

用位操作----异或操作。先全部异或一下得到了99.然后查找99的位置。

#2

递归+折半查找。

这必须知道数组a的所有值的个数(n+1)，而n+1必为奇数。数组a的序号为0到n。

left = 0; right = n; m = (left+right)/2;

int find99(left,right);

m = (n+0)/2,若m为偶数，也即m两边的数量都为偶数，分别判断a[m]与a[m-1]、a[m+1]的值，若与a[m-1]相等，则99必在左侧，那么接下来就find99(left,m-1)。若与a[m+1]相等，则99必在右侧，那么find99(m+1,right)。若都不相等，则a[m] == 99,return m。



若m为奇数，也即m两边的数量都为奇数，分别判断a[m]与a[m-1]、a[m+1]的值，若与a[m-1]相等，则99必在右侧，find99(m+1,right)。若与a[m+1]相等，则99必在左侧，find99(left,m-1)。若都不相等，则a[m] == 99，return m。

#3

引用 1 楼  的回复:

用位操作----异或操作。先全部异或一下得到了99.然后查找99的位置。

我在面试第二天坐在公交上想出来一个答案，这里先不说。
还有别的好方法吗？

#4

我觉得笨笨熊的方法不错。

#5

引用 2 楼  的回复:

递归+折半查找。

这必须知道数组a的所有值的个数(n+1)，而n+1必为奇数。数组a的序号为0到n。

left = 0; right = n; m = (left+right)/2;

int find99(left,right);

m = (n+0)/2,若m为偶数，也即m两边的数量都为偶数，分别判断a[m]与a[m-1]、a[m+1]的值，若与a[m-1]相等，则99必……

厉害，我是第二天才想出来的，想出来才发现这个问题其实很简单，只是当时就是想不出来，要想出来就被录用了。

#6

引用 4 楼  的回复:

我觉得笨笨熊的方法不错。

笨笨熊的办法就是从前到后一个数一个数的比较。直到比较到某个数不相等为止。

#7

引用 5 楼  的回复:

引用 2 楼  的回复:

递归+折半查找。

这必须知道数组a的所有值的个数(n+1)，而n+1必为奇数。数组a的序号为0到n。

left = 0; right = n; m = (left+right)/2;

int find99(left,right);

m = (n+0)/2,若m为偶数，也即m两边的数量都为偶数，分别判断a[m]与a[m-1]、a[m+1]的值……

在这道题中，m能为偶数吗？ 

#8

综合采用1楼和2楼的方法最好 因为前提你是不知道要找的是99的情况。

#9

要找的那个不一定是99,但思想就是二分查找，先取中间那个数
如果index为[0...n]，中间那个数就是 (n+1)/2，具体实现，就循环就行，不一定要用递归。

#10

错了，中间那个数就是 n/2

#11

比如说这个个数组a长度为N，
第一次取：flag = N/2 ,比较a[flag] 和 a[flag+1] ，如果相等，那么要找得数在N/2后面一部分；不等的话那么直接就找到了这个数的位置；

以后继续第一步，递归。。。

#12

#include <stdio.h>

int find(int* array, int size)
{
	int i;
	for (i = 0; i < size; i += 2)
		if (array[i] != array[i + 1])
			return i;
	return -1;
}

int main(void)
{
	int array[] = { 102, 102, 2, 2, 44, 44, 99, 23, 23, 11, 11 };
	printf("%d", find(array, sizeof array / sizeof *array));
	return 0;
}

#13

笨笨熊的方法非常高效简洁，而且对乱序数组有效

#14

楼主既然觉得2楼的方法比较好，能告诉我是为什么？说实话，我到现在还没有看出2楼的方法的正确性！下面分析。
m = (n+0)/2,若m为偶数，也即m两边的数量都为偶数，分别判断a[m]与a[m-1]、a[m+1]的值，若与a[m-1]相等，则99必在左侧，那么接下来就find99(left,m-1)。若与a[m+1]相等，则99必在右侧，那么find99(m+1,right)。若都不相等，则a[m] == 99,return m。
例子：1,2,3,5,4,3,4,2,1  那么m=(9+0)/2=4 a[m]==4 与左右两边都不等。说明4就是要找的？？？显然是错误的嘛。如果楼主觉得这方法是正确的话也难怪楼主去不了公司了。

#15

参考拙作：
一个百度的面试题目

几周前一个坛友问了一模一样的问题，俺就整理成了上面这篇博客。

#16

Sorry，忽视15楼的回答，还是有些不同的。不过思路是可以借鉴的。

#17

随便找个数字a，2次异或相同的数字（数组数字）后必然还是a

不等于跳出循环

#18

那参考这个：

#include <iostream>
using namespace std;

int main(int argc, char* argv[])
{
	int the_number = 0;
	int arr[] = {102, 102, 2, 2, 44, 44, 99, 23, 23, 11, 11};

	// 第一次遍历，找到那个不成对的数字
	for(int i = 0; i < sizeof(arr) / sizeof(int); ++i)
	{
		the_number ^= *(arr + i);
	}

	// 第二次遍历，找到该数字在数组中的位置
	for(int i = 0; i < sizeof(arr) / sizeof(int); ++i)
	{
		if(the_number == *(arr + i))
		{
			cout << "The number is " << the_number << ", which locates at " << i << "." << endl;
			break;
		}
	}

	return 0;
}

时间复杂度就是O(n).

#19

引用 17 楼  的回复:

随便找个数字a，2次异或相同的数字（数组数字）后必然还是a

不等于跳出循环

	int num[7] = {2,2,4,4,9,5,5};
	int optnum , tempnum , count;

	count = sizeof(num)/sizeof(int);

	for(int i=0; i<count; i+=2)
	{
		optnum = tempnum = 100;

		optnum = optnum ^ num[i];
		optnum = optnum ^ num[i+1];

		if(optnum != tempnum)
		{
			printf("位置:%d\n",i);
			break;
		}
	}

#20

引用 14 楼  的回复:

楼主既然觉得2楼的方法比较好，能告诉我是为什么？说实话，我到现在还没有看出2楼的方法的正确性！下面分析。
m = (n+0)/2,若m为偶数，也即m两边的数量都为偶数，分别判断a[m]与a[m-1]、a[m+1]的值，若与a[m-1]相等，则99必在左侧，那么接下来就find99(left,m-1)。若与a[m+1]相等，则99必在右侧，那么find99(m+1,right)。若都不相等，则a……

你有看明白楼主的意思么？成对出现你明白什么意思么？

#21

引用 14 楼  的回复:

楼主既然觉得2楼的方法比较好，能告诉我是为什么？说实话，我到现在还没有看出2楼的方法的正确性！下面分析。
m = (n+0)/2,若m为偶数，也即m两边的数量都为偶数，分别判断a[m]与a[m-1]、a[m+1]的值，若与a[m-1]相等，则99必在左侧，那么接下来就find99(left,m-1)。若与a[m+1]相等，则99必在右侧，那么find99(m+1,right)。若都不相等，则a……

如果为乱序我会想出这种办法？

#22

该回复于2012-06-16 16:43:42被版主删除

#23

我不认为还有谁的算法比二楼的算法更快，他的算法时间复杂度是O（n）。

#24

如果不是乱序，那显然12楼的方法简洁高效
总之2楼的方法是最差的，连正确不正确我都不想检查，这么简单的题答这么长。。。

#25

引用 23 楼  的回复:

我不认为还有谁的算法比二楼的算法更快，他的算法时间复杂度是O（n）。

二分法算法复杂度是O(log2n)，不过对于小量级的数组没必要用

#26

弄错了，一楼算法的时间复杂度是O（n），二楼的是log（n），但二楼的算法只有当成对的数相邻时才能用。

#27

引用 24 楼  的回复:

如果不是乱序，那显然12楼的方法简洁高效
总之2楼的方法是最差的，连正确不正确我都不想检查，这么简单的题答这么长。。。

为什么我的方法是最差的？你举个例子？你就凭我描述的长短来判断方法的好坏么？

你说的话让人很蛋疼。正确不正确都没检查，单凭长短来判断，你还真是个高手。

#28

引用 24 楼  的回复:

如果不是乱序，那显然12楼的方法简洁高效
总之2楼的方法是最差的，连正确不正确我都不想检查，这么简单的题答这么长。。。

你是来搞笑的么？“这么简单的题答这么长”就是你判断方法好坏的依据？谁说这题的数据量小了？

#29

你说对了，判断方法好坏最主要的看是否简洁易懂
只有在确实构成性能瓶颈的地方才需要考虑优化
而是否性能瓶颈应该是通过工具检查，而不是拍脑袋

#30

引用 29 楼  的回复:

你说对了，判断方法好坏最主要的看是否简洁易懂
只有在确实构成性能瓶颈的地方才需要考虑优化
而是否性能瓶颈应该是通过工具检查，而不是拍脑袋

请问2L说的哪里不简洁易懂了？仅仅你看不懂就不是“简洁易懂了”..？
另外真心希望你明白别人的思想以后再来评判别人。

#31

要不一句话写出来思路，要不直接代码表达，一个二分法写成那样就不要自称简洁易懂了
不过不愿意看直接跳过，然后就抨击确实不应该，向2L道歉

#32

还是位运算 异或 比较好，数组的元素只有一个不是成对的，所以把数组元素全部进行 异或 运算得到结果就是要找的那个数。很清楚明了。

+1

#33

二楼的思路要晕上半天。。

#34

粗略的写了一个程序，时间复杂度是O（logn），但要求成对的数字必须是相邻的。
#include <iostream>
using namespace std;

int search_single_num(int *a, int start, int end)
{
int mid;
int start_mid;
int end_mid;
while(start!=end)
{
mid = (start+end)/2;
if(a[mid]==a[mid-1])
{
start_mid = mid;
end_mid = mid+1;
}
if(a[mid]==a[mid+1])
{
start_mid = mid-1;
end_mid = mid;
}
if(a[mid]!=a[mid+1] && a[mid]!=a[mid-1])
{
return mid;
}

if((start_mid-start)%2==0)
{
end = start_mid;
}
else
{
start = end_mid;
}
}
return start;
}

int main()
{
int a[11] = {102, 102, 2, 2, 44, 44, 99, 23, 23, 11, 11};
cout<<search_single_num(a, 0, 10)<<endl;
return 0;
}

#35

引用 14 楼  的回复:

楼主既然觉得2楼的方法比较好，能告诉我是为什么？说实话，我到现在还没有看出2楼的方法的正确性！下面分析。
m = (n+0)/2,若m为偶数，也即m两边的数量都为偶数，分别判断a[m]与a[m-1]、a[m+1]的值，若与a[m-1]相等，则99必在左侧，那么接下来就find99(left,m-1)。若与a[m+1]相等，则99必在右侧，那么find99(m+1,right)。若都不相等，则a[……

按照楼主给的测试用例的意思，好像可以配对的两个数都是相邻的。
……102，102，2，2，44，44，99，23，23，11，11 …… 

#36

这个可以在第一个for()循环修改一下

当i=1，2,3...奇数 且同时the_number ！= 0 的时候就找到了这个数字的下标，下标就是 i-1 ，然后后面的可以不用看了。

引用 18 楼  的回复:

那参考这个：
C/C++ code

#include <iostream>
using namespace std;

int main(int argc, char* argv[])
{
    int the_number = 0;
    int arr[] = {102, 102, 2, 2, 44, 44, 99, 23, 23, 11, 11};

    // 第一次遍历，找……

#37

#include <iostream>
using namespace std;

int main(int argc, char* argv[])
{
	int the_number = 0;
	int arr[] = {102, 102, 2, 2, 44, 44, 99, 23, 23, 11, 11};

	// 第一次遍历，找到那个不成对的数字
	for(int i = 0; i < sizeof(arr) / sizeof(int); ++i)
	{
		the_number ^= *(arr + i);
		if ( ((i+1)%2 == 0)  && the_number != 0)
		{
			cout << "the number is arr["<<i-1<<"]="<<arr[i-1]<<endl;
				break;
		}
	}
	getchar();
	return 0;
}

#38

引用 37 楼  的回复:

C/C++ code


#include <iostream>
using namespace std;

int main(int argc, char* argv[])
{
    int the_number = 0;
    int arr[] = {102, 102, 2, 2, 44, 44, 99, 23, 23, 11, 11};

    // 第一次遍历……

请问你的代码是怎么粘贴的，为什么我的代码贴进来格式全没了

#39

#include <iostream>
using namespace std;

int search_single_num(int *a, int start, int end)
{
int mid;
int start_mid;
int end_mid;
while(start!=end)
{
mid = (start+end)/2;
if(a[mid]==a[mid-1])
{
start_mid = mid;
end_mid = mid+1;
}
if(a[mid]==a[mid+1])
{
start_mid = mid-1;
end_mid = mid;
}
if(a[mid]!=a[mid+1] && a[mid]!=a[mid-1])
{
return mid;
}

if((start_mid-start)%2==0)
{
end = start_mid;
}
else
{
start = end_mid;
}
}
return start;
}

int main()
{
int a[11] = {102, 102, 2, 2, 44, 44, 99, 23, 23, 11, 11};
cout<<search_single_num(a, 0, 10)<<endl;
return 0;
}

#40

我是chrome浏览器+VS2008，就这样复制黏贴的

#41

你应该把代码贴到[code ][/ code]标签的中间

#include <iostream>
using namespace std;

int search_single_num(int *a, int start, int end)
{
int mid;
int start_mid;
int end_mid;
while(start!=end)
{
mid = (start+end)/2;
if(a[mid]==a[mid-1])
{
start_mid = mid;
end_mid = mid+1;
}
if(a[mid]==a[mid+1])
{
start_mid = mid-1;
end_mid = mid;
}
if(a[mid]!=a[mid+1] && a[mid]!=a[mid-1])
{
return mid;
}

if((start_mid-start)%2==0)
{
end = start_mid;
}
else
{
start = end_mid;
}
}
return start;
}

int main()
{
int a[11] = {102, 102, 2, 2, 44, 44, 99, 23, 23, 11, 11};
cout<<search_single_num(a, 0, 10)<<endl;
return 0;
}

引用 39 楼  的回复:

#include <iostream>
using namespace std;

int search_single_num(int *a, int start, int end)
{
int mid;
int start_mid;
int end_mid;
while(start!=end)
{
mid = (start+end)……

#42

#include <iostream>
using namespace std;

int search_single_num(int *a, int start, int end)
{
int mid;
int start_mid;
int end_mid;
while(start!=end)
{
mid = (start+end)/2;
if(a[mid]==a[mid-1])
{
start_mid = mid;
end_mid = mid+1;
}
if(a[mid]==a[mid+1])
{
start_mid = mid-1;
end_mid = mid;
}
if(a[mid]!=a[mid+1] && a[mid]!=a[mid-1])
{
return mid;
}

if((start_mid-start)%2==0)
{
end = start_mid;
}
else
{
start = end_mid;
}
}
return start;
}

int main()
{
int a[11] = {102, 102, 2, 2, 44, 44, 99, 23, 23, 11, 11};
cout<<search_single_num(a, 0, 10)<<endl;
return 0;
}

#43

[code=#include] <iostream>
using namespace std;

int search_single_num(int *a, int start, int end)
{
int mid;
int start_mid;
int end_mid;
while(start!=end)
{
mid = (start+end)/2;
if(a[mid==a[mid-1])
{
start_mid = mid;
end_mid = mid+1;
}
if(a[mid]==a[mid+1])
{
start_mid = mid-1;
end_mid = mid;
}
if(a[mid]!=a[mid+1] && a[mid]!=a[mid-1])
{
return mid;
}

if((start_mid-start)%2==0)
{
end = start_mid;
}
else
{
start = end_mid;
}
}
return start;
}

int main()
{
int a[11] = {102, 102, 2, 2, 44, 44, 99, 23, 23, 11, 11};
cout<<search_single_num(a, 0, 10)<<endl;
return 0;
}][/code]

#44

#include <iostream>
using namespace std;

int search_single_num(int *a, int start, int end)
{
	int mid;
	int start_mid;
	int end_mid;
	while(start!=end)
	{
		mid = (start+end)/2;
		if(a[mid]==a[mid-1])
		{
			start_mid = mid;
			end_mid = mid+1;
		}
		if(a[mid]==a[mid+1])
		{
			start_mid = mid-1;
			end_mid = mid;
		}
		if(a[mid]!=a[mid+1] && a[mid]!=a[mid-1])
		{
			return mid;
		}

		if((start_mid-start)%2==0)
		{
			end = start_mid;
		}
		else
		{
			start = end_mid;
		}
	}
	return start;
}

int main()
{
	int a[11] = {102, 102, 2, 2, 44, 44, 99, 23, 23, 11, 11};
	cout<<search_single_num(a, 0, 10)<<endl;
	return 0;
}

#45

这个是UBB代码，这些标签像HTML/XML语言的 <></> 标签，要格式化的内容写在中间就行了

引用 42 楼  的回复:

#include <iostream>
using namespace std;

int search_single_num(int *a, int start, int end)
{
int mid;
int start_mid;
int end_mid;
while(start!=end)
{
mid = (start+end)/2……

#46

#include <iostream>
using namespace std;

int search_single_num(int *a, int start, int end)
{
	int mid;
	int start_mid;
	int end_mid;
	while(start!=end)
	{
		mid = (start+end)/2;
		if(a[mid]==a[mid-1])
		{
			start_mid = mid;
			end_mid = mid+1;
		}
		if(a[mid]==a[mid+1])
		{
			start_mid = mid-1;
			end_mid = mid;
		}
		if(a[mid]!=a[mid+1] && a[mid]!=a[mid-1])
		{
			return mid;
		}

		if((start_mid-start)%2==0)
		{
			end = start_mid;
		}
		else
		{
			start = end_mid;
		}
	}
	return start;
}

int main()
{
	int a[11] = {102, 102, 2, 2, 44, 44, 99, 23, 23, 11, 11};
	cout<<search_single_num(a, 0, 10)<<endl;
	return 0;
}

#47

终于成功了，大家见笑了！

#48

在这里感谢smsgreenlife，ranchenwei，我也接受regainworld的道歉，CSDN是大家交流思想的平台，不是互相攻击的渠道。

我的方法我感觉描述的很清楚了，愿意看的静下心来仔细看看，很简单的一个东西，二分法并非只能用在递增或者递减的数组里，像楼主描述的问题完全可以用二分法来解决，因为这个数组从某种意义上来说完全可以理解为有序数组。

不愿意看的请无视，但是不要在完全没搞清楚状况的情况下凭个人感觉来判断方法的好坏，并且还做出绝对的判断，那就显得相当的幼稚。

#49

如果这个数组 相同的数字都是连续的，何不简单点，只要判断某数字与2旁的数字相同否，有一个相同说明该数字不是要找的数字。

如果这个数组 相同的数字不是连续的，二分是不错，或者我们可以用一个 数据结构来帮助我们存贮已经比对过的数字， 从头到尾走一遍该数组，如果第一次碰到该数字，数字和地址存进数据结构，第2次碰到把该数字从数据结构中移除，最后剩下的就是 要求的数字和地址。

#50

引用 1 楼  的回复:

用位操作----异或操作。先全部异或一下得到了99.然后查找99的位置。

异或操作为什么可以呢？不明白。。。。。