{1,22,56,53,34,51,77}这是一个数组，如何不用内部函数和遍历数组的方法判断出 53 在这个数组里。（面试问题）

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3458 天前的主题，其中的信息可能已经有所发展或是发生改变。

我想到了php中的in_array()函数。但是很明显不对。

数组

函数

PHP

119 条回复 • 2015-07-13 10:50:44 +08:00

1 2

❮

❯

101

ant_sz

2015-07-11 19:40:49 +08:00

我觉得楼上有提出来既然数组是给定的，那么我们自己先吧乘积（在计算机之外）算出来，然后看看是不是整除确实是一种可以说的过去的方法。因为在其他某些算法中也有类似这样预先定义好常数的方法。

然而如果这道题真的是这个意思，那么这道题和这个算法其实都没有什么卵用。一个用脑筋急转弯题要求面试者提供一个不能通用的函数的企业最好还是敬而远之。

102

codercai

2015-07-11 20:02:04 +08:00

@nozama 看来看去，你这个本质上依然是遍历呀，和在for循环中依次条件测试没有什么区别，依次检查了53出现之前的所有元素

103

codercai

2015-07-11 20:08:44 +08:00

@ningyuqiao456 楼主你再看看，nozama的方法和遍历没有两样好嘛，仍然是依次遍历了目标53出现之前的所有元素。此题，貌似不遍历不行，至少遍历一部分

104

codercai

2015-07-11 20:12:13 +08:00

@ant_sz 然而乘积也是要遍历所有元素的呀

105

codercai

2015-07-11 20:16:36 +08:00

@latyas XOR“原始数组”不需要遍历么？，不便利如如何提取数组元素

106

latyas

2015-07-11 20:42:47 +08:00

@codercai 不用遍历啊，对折取XOR，假设支持无限长度的内存，23333

107

nozama

2015-07-11 20:50:01 +08:00

@codercai 一般所说的“遍历”，应该是“在运行时循环”的意思，递归本质也是循环。所以我刚想到另一个办法, 用！模！板！：
(每次调用的find都不是同一个函数...所以不是递归，也不是循环...）

template<int N>
bool find(int num, int* arr)
{
std::cout << N << " ";
if(arr[N] == num) return true;

return find<(N-1)>(num, arr);
}

template <>
bool find<0>(int num, int* arr)
{
return false;
}

void main()
{
auto found = find<6>(55, arr);
}

108

nozama

2015-07-11 20:56:36 +08:00

修正
template<int N>
bool find(int num, int* arr)
{
if(arr[N] == num) return true;

return find<(N-1)>(num, arr);
}

template <>
bool find<-1>(int num, int* arr)
{
return false;
}

int main()
{
int arr[] = {1,22,56,53,34,51,77};
auto found = find<6>(1, arr);

assert(found);
}

109

2015-07-11 20:59:08 +08:00

为什么会有这个数组?Who set it ? Or it just someone set here ? Why not go to ask the man who set this rule :)

110

laoyuan

2015-07-11 21:20:19 +08:00

各种跪！

111

tushiner

2015-07-11 22:55:17 +08:00

问题的关键在于“取出元素”，只要取出来了，判断是53就算完成任务了。。。
var arr = [1,22,56,53,34,51,77];
var timer = setInterval(function(){
if(arr[Math.floor(Math.random()*arr.length)]==53)clearInterval(timer);
},250);

112

realpg

2015-07-11 23:16:42 +08:00

这不是PHP节点么，楼上的大多数们难道没有发现？

$arr=array(1,22,56,53,34,51,77);
$ret=testArray($arr);
die($ret);

function testArray($array) {
$str=implode($array);
if (strpos(str,'5')===false) return false;
return true;
}

113

ant_sz

2015-07-11 23:47:23 +08:00

@codercai

然而乘积的结果可以作为一个常数直接硬编码到代码里。。。这就是我说的在计算机之外算。最后写出来的程序实际上等价于直接return true。。。因为除了用来判断 53 在里面之外没有任何其他可用之处。

确实有一些算法是允许直接放这样的常量进去的。比如我们要reverse一个32bit的integer，可以先吧他分成四个8bit的组，每一组直接用硬编码的逆转表来查。这种方法在reverse integer这个问题里是合适的。所以我觉得放在这个茶53的问题里也勉强可以接受。

只是觉得出这种题的企业真是蛋疼。。。应该把名字告诉大家让大家果断绕道。。。

114

tuutoo

2015-07-11 23:54:49 +08:00

C#的，PHP不知道能做到吗。。

class Program
{
static void Main(string[] args)
{
int[] intArray = { 1, 22, 56, 53, 34, 51, 77 };
Dictionary<int, bool> dictionary = intArray.ToDictionary(v => v, v => true);

Console.WriteLine(dictionary.ContainsKey(53));
Console.ReadKey();
}
}