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

poiu710 2012-06-16 09:31:03

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

...全文

2589 106 打赏收藏转发到动态举报

写回复

用AI写文章

106 条回复

切换为时间正序

请发表友善的回复…

发表回复

zhenguo_lee 2012-06-20

打赏
举报

#include <stdio.h>



static const int array[] = { 100, 100, 20, 20, 11, 11, 44, 44, 55, 55, 99, 23, 23, 45, 45, 67, 67 };



static const int find_single(const int *src, const int *dest)

{

        if (*src != *dest)

                return *src;

        if (*src == *dest)

                return find_single(src + 2, dest + 2);

        return -1;

}



int main(void)

{

        int ret;



        ret = find_single(array, array + 1);

        if (ret != -1)

                printf("ret: %d\n", ret);

        else

		;



        return 0;

}

jallyx 2012-06-20

打赏
举报

[Quote=引用 104 楼的回复:]

二分法，怎么分？根本就不行，例如：1,2,2,2,2和2,2,2,2,1类似于这两个数组，有哪个高手可以用二分和递归告诉我怎么做？谢谢
[/Quote]



int find(int array[], uint length) {

  if (length <= 1)

    return 0;

  uint begin = (length >> 1) & ~1;

  uint end = begin;

  while (1) {

    if (++end >= length)

      return find(array, begin - 1);

    if (array[begin] == array[end]) {

      if (begin == 0) {

        ++end;

        return end + find(array + end, length - end);

      }

      --begin;

      if (array[begin] != array[end]) {

        if (begin & 1) {

          ++end;

          return end + find(array + end, length - end);

        } else {

          return find(array, begin + 1);

        }

      }

    } else {

      if (begin & 1)

        return end + find(array + end, length - end);

      else

        return find(array, begin + 1);

    }

  }

}

综合二分和遍历方法。
顺带拿分闪人。

景语 2012-06-20

打赏
举报

学习了

MeAndJack 2012-06-20

打赏
举报

二分法，怎么分？根本就不行，例如：1,2,2,2,2和2,2,2,2,1类似于这两个数组，有哪个高手可以用二分和递归告诉我怎么做？谢谢

MeAndJack 2012-06-20

打赏
举报

[Quote=引用 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必……
[/Quote]

这个方法根本就是不行的，如果出现的数组是 2,2,2,2,2,2,2,2,1这样的数组呢，那肯定是无法递归下去的，楼主想得太简单了。。。。。。这个问题只能用异或来解决

vanxining 2012-06-20

打赏
举报

[Quote=引用 74 楼的回复:]

提问2#，请问M怎么会为奇数？？m=(n+0)/2。。不管n是奇数还是偶数，m不都是偶数吗？？？
再说了，设一共有n+1个数，那么n一定是偶数，请问若原数组元素个数是偶数的话，怎么可能只有一个不配对，其他的都是两两成对？？？？
[/Quote]
很明显，按照题意，m肯定是偶数的啦，我在麦库中记录这道题时就直接删了二楼关于m为奇数的那部分讨论

rustydaar 2012-06-19

打赏
举报

[Quote=引用 74 楼的回复:]

提问2#，请问M怎么会为奇数？？m=(n+0)/2。。不管n是奇数还是偶数，m不都是偶数吗？？？
再说了，设一共有n+1个数，那么n一定是偶数，请问若原数组元素个数是偶数的话，怎么可能只有一个不配对，其他的都是两两成对？？？？
[/Quote]

m为什么一定会是偶数？除2得到的不一定是偶数。

pupingpp 2012-06-19

打赏
举报

[Quote=引用 78 楼的回复:]

居然楼中这么多人喷2楼。。
喷二分查找的筒子支持的那个算法，顶天也是O(n)，二分查找是O(lgn)。
这种行为犹如是在坚决支持冒泡排序，排斥快排，仅仅是因为快排不能一下子就能被理解
承认自己的错误不是什么难事，何况在网络上~
[/Quote]
能不能解释一下我提出的问题啊？谢谢了，我不是有意喷二楼，我只是想搞明白，因为马上就要毕业找工作呢，说不定还会遇到这样的题目啊。。。感谢

vanxining 2012-06-19

打赏
举报

[Quote=引用 58 楼的回复:]

引用 15 楼的回复:

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

几周前一个坛友问了一模一样的问题，俺就整理成了上面这篇博客。
这里我要说声抱歉，是我题目没有说清楚，成对，且相邻的。这个题是我10年12月(好像是12月，记不清了)广州大学城北亭广场现场面试题。
[/Quote]
真古老啊，亏楼主还记得

c090869 2012-06-19

打赏
举报

试了两种方法，发现用位操作速度慢；
int i,j,k,a=10,b=10;
for(i=0;i<10000;i++)
for(j=0;j<10000;j++)
for(k=0;k<50;k++)
{
if(a^=b) a=10; // if(a==b) a=10;
}
printf("i=%d,%d.%d\n";i,j,k);

vanxining 2012-06-19

打赏
举报

居然楼中这么多人喷2楼。。
喷二分查找的筒子支持的那个算法，顶天也是O(n)，二分查找是O(lgn)。
这种行为犹如是在坚决支持冒泡排序，排斥快排，仅仅是因为快排不能一下子就能被理解
承认自己的错误不是什么难事，何况在网络上~

modicum_lf 2012-06-19

打赏
举报

[Quote=引用楼主的回复:]
题目大意：
有这样一个数组，除其中一个元素（如下面的99），其它的都是成对出现的，如何能快速找出那99的位置
……102，102，2，2，44，44，99，23，23，11，11 ……
[/Quote]

++

kangyuanxun 2012-06-19

打赏
举报

[Quote=引用 1 楼的回复:]

用位操作----异或操作。先全部异或一下得到了99.然后查找99的位置。
[/Quote]
全部异或？效率多少？还是二分查找好

youngwolf 2012-06-19

打赏
举报

注意这个问题与排序与否真的没有一点关系，你只需要折半比较两个数，根据它相同与否，以及位置的奇偶性，就知道答案是在前面的子数组还是后面的子数组（二分法）

youngwolf 2012-06-19

打赏
举报



void do_find_the_one_diff(int in_data[], size_t len, size_t index)

{

	if (0 == index)

	{

		cout << "find the only diff: " << in_data[index] << endl;

		return;

	}



	if (in_data[index - 1] != in_data[index])

	{

		len -= index;

		in_data += index;

	}

	else

		len = index - 1;



	index = len >> 1;

	if (index & 1)

		++index;

	do_find_the_one_diff(in_data, len, index);

}



void find_the_one_diff(int in_data[], size_t len)

{

	if (len & 1)

	{

		size_t index = len >> 1;

		if (index & 1)

			++index;

		do_find_the_one_diff(in_data, len, index);

	}

}



int main()

{

	int in_data[] = {1, 1, 3, 3, 2, 4, 4, };

	size_t len = sizeof in_data / sizeof(int);

	find_the_one_diff(in_data, len);

	return 0;

}

最快当然是二分查找，根本不需要遍历，不需要存储。

风吹过的卫星 2012-06-19

打赏
举报

其实不需要这么复杂，设两个相邻索引的指针，同时通过索引递增，当两个索引值不同时就找到了，位置也就确定了

ranchenwei 2012-06-19

打赏
举报

[Quote=引用 91 楼的回复:]

稍微看了下回复，怎么那么多人说用二分查找？二分查找是针对有序序列的，请问下楼主说得题目，没说明数组是有序吧？
[/Quote]

请仔细看一下题目以及二分的思路，这题二分不能处理的情况在于重复元素而不是无序。

nice_cxf 2012-06-19

打赏
举报

在85楼已经说过了，折半是有前提的：数对不能重复，也就是说不允许1，1，1，1这种
否则假定100个1，1个99，你往那边折啊？

Canvas 2012-06-19

打赏
举报

[Quote=引用 93 楼的回复:]
引用本人的回复:

递归+折半查找。

这必须知道数组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]的值，若与……
[/Quote]

折半查找需要的是有序....
等你把数组有序得来，结果都出来了

qixing1115 2012-06-19

打赏
举报

[Quote=引用本人的回复:]

递归+折半查找。

这必须知道数组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必……
[/Quote]
折半