腾讯面试：猴子偷吃了哪根香蕉？

来源丨经授权转自 爱码有道（ID：aimayoudao）

作者丨爱码有道

大家好，我是道哥。今天，我们来聊一道腾讯面试的题目。

不要觉得腾讯的面试题一定很难，当然，也不要掉以轻心地觉得它很简单，一起来看看题目：

有n根香蕉，分别编号1~n, 无序地放在一起。夜晚，一只猴子偷吃了其中的1根香蕉。第二天早晨，管理员生气了，他该怎样找出被偷吃的香蕉的编号呢？请编程求解。

方法一: 数学计算

我们来看看偷吃前后的变化：

显然，原来的和是：

2+4+1+3=10

后来的和是：

2+1+3=6

他们的差是：

10-6=4

所以，被偷吃的香蕉的编号就是4. 想到这里，你可能不禁感慨，腾讯的面试题会这么简单吗？显然，这种解法是有问题的，也是无法通过面试的。

为什么呢？如上总共只有4个香蕉，即n=4, 一旦n的值非常大，上述的加法计算，可能导致整数越界。所以，利用加法计算，并不是很好的方法。

方法二: 排序算法

我们对剩下来的香蕉进行排序：

排序后，我们遍历1~n, 看看数字在哪个地方断开了，很显然，在4这里断开了，所以被吃的香蕉的编号就是4.

一般来说，应聘者应该有这样一种直觉，很多时候，如果需要通过排序来做，那么这个方法很可能不是最优的。

在该问题中，无论是用哪种排序算法，时间复杂度和空间复杂度都无法达到最优，显然，也是无法通过面试的。

方法三: 异或算法

我们再来看看偷吃前后的变化：

我们考虑对虚线框中的数进行异或，很显然，x与x的异或值是0，又由于异或可交换可结合，所以，可以把上述所有的数字进行异或，最后的值就是4，且看：

x = 2^4^1^3^2^1^3

利用异或的交换律和结合律：

x = (2^2)^4^(1^1)^(3^3)

也即：

x = (0)^4^(0)^(0)=4

这种异或运算很巧妙，时间复杂度是O(n), 空间复杂度是O(1)，也是最佳的算法，能通过面试。接下来，我们来编程计算x的值，即

x = 1^2^3^4^2^1^3

编程实现

C++程序如下：

#include <iostream>using namespace std;
int main(){ int n = 4; int a[3] = {2, 1, 3}; // 被偷吃后的香蕉号 int x = 0; for (int i = 1; i <= n; i++) { x ^= i; // 原来的异或值 } for (int i = 0; i < n - 1; i++) { x ^= a[i]; } cout << x << endl; return 0;}

结果：4

异或运算的思路挺巧妙。我们也会一步一个脚印，争取每篇文章讲清讲透一件事，也希望大家阅读后有所收获，心情愉快。

点分享

点点赞

点在看