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

数组

函数

PHP

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

1 2

❮

❯

1

adspe

2015-07-10 22:07:09 +08:00 via iPad

用查找算法？

2

qiayue

2015-07-10 22:09:49 +08:00

用 implode 合并成逗号分隔的字符串，然后判断字符串？
任何 php 内部函数都不能用吗还是说仅仅不能用同功能的函数？

3

simman

2015-07-10 22:13:31 +08:00

public static function inArray($item, $array) {
$flipArray = array_flip($array);
return isset($flipArray[$item]);
}

这个？？？

4

xlmo

2015-07-10 22:18:13 +08:00

不用内部函数？那貌似只能一个一个去if($arr[0] == 53) 了。。

5

whahuzhihao

2015-07-10 22:20:04 +08:00

array_flip也是内部函数啊

6

iyaozhen

2015-07-10 22:26:49 +08:00

应该就是考查找算法吧。

7

dallaslu

2015-07-10 22:39:37 +08:00

1

针对这个数组进行任何处理，都有可能进行遍历的吧！

如果不需要遍历，不如生成一个 0 到数组长度 -1 随机数，来随机读取数组内元素，每次保证不重复读取相同位置上就行了。这样有七分之一的概率不需要遍历数组。

8

br00k

2015-07-10 22:44:59 +08:00

不遍历怎么知道？？感觉这种问题怎么有点弱智啊。。。

9

est

2015-07-10 22:45:19 +08:00

1

赌10元钱任何实现都用到了某种程度上的遍历。

10

choury

2015-07-10 22:46:04 +08:00

不管用什么方法到最后都是要遍历的，至少得知道里面有那些元素吧
除非能找到一个公式可以生成这个序列，不然不可能的

11

lincanbin

2015-07-10 22:51:38 +08:00 via Android

不让遍历的意思就是不让你逐个看这里面的东西吧。
PHP内部函数1500个都不让用，又不让看。
这是什么鬼？

12

mouhong

2015-07-10 22:51:42 +08:00

@dallaslu 随机数生成，重复读取判断，这貌似增加复杂度了吧。数组本身无序，已经存在不需要遍历的可能性了吧。要是可接受近似解，貌似有个什么亚线性算法可以用，具体不知了

13

loveuqian

2015-07-10 22:52:20 +08:00 via iPhone

@xlmo 那也是遍历啊

14

mouhong

2015-07-10 22:53:02 +08:00

@mouhong 不过这种题感觉就是考个遍历，传说中的 FuzzBuzz 测试

15

solupro

2015-07-10 22:55:06 +08:00

1

我们可以用in呀
http://nikic.github.io/2012/07/27/How-to-add-new-syntactic-features-to-PHP.html

---
好吧，上面开玩笑的，也是遍历，求正确姿势

16

hobbyliu

2015-07-10 22:56:33 +08:00

@dallaslu 此方法，不错，忘记叫什么算法了，概率性很大。

17

r00tt

2015-07-10 22:59:31 +08:00

@hobbyliu 是蒙特卡洛么，有点这个的感觉

18

hobbyliu

2015-07-10 23:02:39 +08:00

@leepood 不是，我记得当初的一个场景时，一个猴子为了排序3个大小不同的干果，不断的往天上抛，直到，排序正确位置，适用于少量元素排序，概率性很大。

19

sumhat

2015-07-10 23:03:20 +08:00

$array = {1,22,56,53,34,51,77};

if (TRUE || array) {
echo '我灵光一闪，断定 53 必然在这个数组里。';
}

20

101

2015-07-10 23:04:48 +08:00

查找算法也是要遍历的呀

21

Septembers

2015-07-10 23:11:25 +08:00 via Android

@est 构造随机数作为索引随机命中如果匹配就。。。。。？

22

ning1022

OP

2015-07-10 23:13:32 +08:00

@adspe 感觉考察的是算法。但是我不也不会！

23

ning1022

OP

2015-07-10 23:14:05 +08:00

@qiayue 应该是同功能的函数，比如in_array()

24

est

2015-07-10 23:14:22 +08:00

1

@Septembers 文字上可以不叫遍历，本质上不也是挨着挨着一个一个问么。

25

ning1022

OP

2015-07-10 23:15:24 +08:00

@simman 我感觉这个不是正确答案！

26

ning1022

OP

2015-07-10 23:18:46 +08:00

@est 我要是面试成功的话，我一定问问他这个答案，我很无语，查了很多资料，感觉是算法。

27

ning1022

OP

2015-07-10 23:20:35 +08:00

@mouhong 大数据算法？感觉有点抽象！

28

ning1022

OP

2015-07-10 23:22:57 +08:00

@Septembers 这个是个好思路，哈哈！

29

dingyaguang117

2015-07-10 23:23:18 +08:00

可以反证必须要遍历的

30

Septembers

2015-07-10 23:27:56 +08:00 via Android

@ningyuqiao456 @mouhong 说的是模糊测试
see https://zh.wikipedia.org/wiki/模糊测试

31

hackpro

2015-07-10 23:30:57 +08:00

@dallaslu 正解某年acm切的題
如果特別考察你算法的話翻翻拓撲的東西以前數學課上過現在記不清了

32

nozama

2015-07-10 23:31:46 +08:00

bool find1(int num, int index, int* arr)
{
return num == arr[index];
}
bool find3(int num, int base_index, int* arr)
{
return find1(num, base_index, arr) || find1(num, base_index + 1, arr) || find1(num, base_index + 2);
}

bool find6(int num, int base_index, int* arr)
{
return find3(num, base_index, arr) || find3(base_index + 4);
}

int main()
{
int arr[] = {1,22,56,53,34,51,77};
auto found = find1(53, arr) || find6(53, 1, arr);
}

33

nozama

2015-07-10 23:35:14 +08:00

随手写的，有些typo

34

ning1022

OP

2015-07-10 23:37:13 +08:00

@Septembers 我感觉他考的是效率或者算法。当时我还想到了二叉树，从中间分，log2N。（以前考计算机二级的时候学的，现在都忘了，不知道对不对，呵呵）

35

zhaiduo

2015-07-10 23:39:11 +08:00 via Android

78

36

imyip

2015-07-10 23:42:34 +08:00 via Android

二分法？

37

ning1022

OP

2015-07-10 23:42:47 +08:00

@nozama 你这好像没有遍历也没有内部函数，牛呀，但是我得抽空测试下，这个好像是C写的。

38

dallaslu

2015-07-10 23:46:15 +08:00

@ningyuqiao456 如果数组有序，二分还可以

39

nozama

2015-07-10 23:46:34 +08:00

@ningyuqiao456 我测试过了，应该没错。
//====================
bool find1(int num, int index, int* arr){ return num == arr[index]; }

bool find3(int num, int base_index, int* arr){ return find1(num, base_index, arr) || find1(num, base_index + 1, arr) || find1(num, base_index + 2, arr); }

bool find6(int num, int base_index, int* arr){ return find3(num, base_index, arr) || find3(num, base_index + 4, arr); }

bool find7(int num, int* arr, size_t size){ return find1(num, 0, arr) || find6(num, 1, arr); }

int main()
{
int arr[] = {1,22,56,53,34,51,77};

auto found = find7(53, arr, sizeof(arr));

assert(found);
}

40

mulog

2015-07-10 23:46:40 +08:00

我觉得需要定义一下遍历。。。

41

ning1022

OP

2015-07-10 23:53:27 +08:00

@nozama 牛，崇拜！

42

luoxun

2015-07-10 23:54:50 +08:00

array_flip
然后 array_key_exists
应该最快吧 ?

43

Hashell

2015-07-10 23:58:21 +08:00

http://3v4l.org/AdKW4

递归

44

ning1022

OP

2015-07-10 23:59:37 +08:00

@luoxun 这个用了php内部函数了，我感觉会快些，因为用数字查询比较吧，但是跟in_array()相比也没啥区别！

45

sandideas

2015-07-11 00:01:35 +08:00

那个随机数的为什么不直接遍历前6个。。
这样也有七分之一的概率不需要遍历所有。。。

46

ning1022

OP

2015-07-11 00:02:37 +08:00

@Hashell 这个方法好，我看了，可以，感觉递归有可能是正确答案，但是好像这也是一种遍历！

47

luoxun

2015-07-11 00:05:33 +08:00

@sandideas 如果是面试我觉得递归和 array_flip 都应该算是正解起码说得过去

48

Felldeadbird

2015-07-11 00:16:33 +08:00

递归算遍历吗？我只想到递归了。

49

ghostcat

2015-07-11 00:17:28 +08:00

以前我面试也被问了这个问题……实在想不出比遍历更快的方法，然后一直不知道答案

50

sandideas

2015-07-11 00:29:16 +08:00 via iPhone

@luoxun 基本上就是递归了。。。不过这个的递归想不到什么巧妙的方法。直接简单的递归太没意思了

51

sablib

2015-07-11 00:33:09 +08:00

请定义遍历。。。
如果说 ·遍历· 是指按照索引顺序的话，那当然是可以做到不用·遍历·。。。

52

procen424

2015-07-11 00:42:43 +08:00 via Android

如果说遍历是指完整的访问了每一个数，那么对于某些数，只访问其中的一部分二进制位（最少为 1 个位）是不是一种符合条件的解法？
比如说，用每个数的最低位与待查找数的最低位做位与，相同的挑出来，再比较次低位，以此类推。
对于这个题来说，如果是 int32 的数组，共 224 个 bit，读取了其中的 44 个 bit 之后确认了 53 的存在，仅仅访问了 19.6% 的数据，是不是不算是严格意义上的遍历呢。
当然实际情况下你只能按字节读取，即便这样也仅访问了 35.7% 的数据而已。
然并卵，你硬说它是遍历它确实也是。。。

53

Reficul

2015-07-11 00:44:50 +08:00 via Android

递归是遍历的一种方法而已啊，类似遍历二叉树，可以有递归或者非递归的两种算法。这个题目用递归写本质上还是遍历了哇，并且占有内存上还比直接一个个读来的大= =

54

feiyuanqiu

2015-07-11 01:03:10 +08:00

我觉得出题人是想考楼主手写排序和二分的，估计是题目没写清楚...
递归也算遍历，但是没办法，这个题不用遍历做不了
写了一个递归的：

$arr = [1, 22, 56, 53, 34, 51, 77];

function _find($arr, $search, $left, $right)
{
if ($left > $right)
return false;

$pivot = rand($left, $right);
return $arr[$pivot] == $search
? true
: _find($arr, $search, $left, $pivot-1) || _find($arr, $search, $pivot+1, $right);

}

$found = _find($arr, 53, 0, count($arr)-1);

http://3v4l.org/FFFZp

55

Andiry

2015-07-11 01:34:10 +08:00 via Android

@procen424 思路不错，不过现在CPU cache都是64byte，你读int的一个字节等于读了整个int

56

zhangsoledad

2015-07-11 02:19:19 +08:00

不用遍历我也是笑了这是数组不是hash 面试官傻逼别跟着一帮人学过数据结构么？

57

ChangxuBlack

2015-07-11 02:22:57 +08:00

1

建议楼主了解一下布隆过滤器

58

Septembers

2015-07-11 05:20:14 +08:00

@ChangxuBlack
Bloom Filter的大致原理是先遍历一次计算得到 HashSet
第二次通过索引HashSet直接命中目标元素所以仍然无法避免遍历
see https://en.wikipedia.org/wiki/Bloom_filter

我前面提到的方法："构造随机数作为索引随机命中" 理论理想的情况下可以避免遍历

@zhangsoledad PHP的array在Zend Engine的实现就是HashTable
see https://github.com/reeze/tipi/blob/master/book/chapt03/03-01-00-variables-structure.markdown#二变量的值存储

59

Andiry

2015-07-11 06:09:38 +08:00

@ChangxuBlack 单给你一个数组哪来的bloom filter

@Septembers 你这个跟遍历没有区别，期望值是一样的

60

jesse0628

2015-07-11 06:29:25 +08:00

hash table 不行？

61

proudzhu

2015-07-11 09:33:48 +08:00 via Android

53 不就在这个数组里吗，一眼就能看出来，实在要写就来个 return array[3] == 53

62

yuankui

2015-07-11 10:32:21 +08:00

需求不明,你可以反问面试官几句
一帮助您正确理解题意

63

kn007

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

不可能没有遍历。。。看到有人说递归。。。递归不也是遍历。。。$i++。。

64

ant_sz

2015-07-11 11:50:31 +08:00

我觉得蒙特卡洛算法正解。

虽然这个算法的期望时间复杂度很高，但是来保证一定可以判断某个数字是否在array里。比如说我们把每次随机生成的下标保存在HashSet里，如果某次随机生成的下标已经在集合里我们就抛弃他。这样经过足够长的时间我们总能100%的确定53是不是在array里。（当集合size和array 的 size 相同的时候结束算法）。

65

ant106

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

搞不懂什么目的？

var a = [1, 2, 3, 4, 5, 6, 7];
console.log((',' + a.toString() + ',').indexOf(',3,') > 0);

转成字符串用indexOf 算内部函数？

66

WispZhan

2015-07-11 12:48:00 +08:00

要求不遍历，就是二分查找了。二分查找只有最差的情况才是遍历
排序已经遍历了。不遍历根本不能那个排序

67

best1a

2015-07-11 13:40:48 +08:00

@ant_sz +1 上面说的递归和字符串啥的，其实都算遍历的一种了

68

weyou

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

不让遍历无解，那是魔术师干的事情。

69

weyou

2015-07-11 13:48:53 +08:00

就算是人工一眼看出53在里面，也包含了目光的遍历。

70

tushiner

2015-07-11 13:58:38 +08:00

@proudzhu 大亮！

71

killerv

2015-07-11 14:19:29 +08:00

感觉这个比较问题扯啊，明明是个简单的问题非要复杂化。

72

sirgod

2015-07-11 14:23:50 +08:00

注意到53是素数所以全部乘起来再模53看是否等于0就好了

73

myywin

2015-07-11 14:25:20 +08:00

排序，二分？

74

laoyuan

2015-07-11 14:26:04 +08:00

@sirgod 终于出现正确答案了。

75

013231

2015-07-11 14:34:17 +08:00

@sirgod
@laoyuan
你们打算怎样把数组全部乘起来?

76

VicYu

2015-07-11 14:40:29 +08:00

53素数，全乘，摸53，判断是否为0

77

jimiton

2015-07-11 14:40:42 +08:00

@sirgod
全部乘起来，不是得遍历一遍，取出数字相乘么？
相比较遍历一遍，取数比较，有什么优势

78

znoodl

2015-07-11 14:43:48 +08:00 via iPad

@sirgod
@laoyuan
本来遍历到一半就能确认的问题，非要遍历一遍算积再除

79

sketch33

2015-07-11 14:45:28 +08:00

笑死人了，还tm正确答案，真不知道是不是高级黑……

80

sketch33

2015-07-11 14:47:17 +08:00

这个肯定要遍历的啊，就算完全不懂编程好了，假设里面100个元素，使用某种手段访问了其中99个，发现没找到这个数字，那么剩下那个数字你是访问呢还是不访问呢

81

Clarencep

2015-07-11 15:02:34 +08:00

1

遇到这种公司，直接拜拜是最好的选择；要是进去了，还不知道会遇到什么213的产品经理呢，到那时就欲哭无泪了。

82

kurtis

2015-07-11 15:26:32 +08:00

1

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

答：function checkIf53Exist() { return true;}

！！！！！！！！！重要！！！！！！！！！！！

已知条件里已经包含53了，又没有问你任意数组，你们还争论遍历和查找个毛啊，典型的审题不清。
都是程序猿思维，我要是考官，给我说算法的人，统统OUT。

83

laoyuan

2015-07-11 15:44:50 +08:00

@013231 @znoodl @sketch33
怎么乘？当然是用计算器了，难不成口算？？！

function check_in_array($prime, $product) {return !($product % $prime);}
var_dump(check_in_array(53, 8718191328));

完美解决！

84

laoyuan

2015-07-11 15:46:25 +08:00

看那乘积，果然是大数据！

85

hooluupog

2015-07-11 15:57:21 +08:00

一般面试考这类东西都是考算法的。
所以这个题十有八九是让你给出一个时间复杂度小于O(n)的算法来找出某个元素。
有序数组，直接2分查找；
部分有序或者是循环有序数组，也是采用划分的思想，不过需要确定单调区间来决定每次查找的区间。
楼主给的这个数组感觉有问题啊。

86

justahappy

2015-07-11 16:08:53 +08:00

@laoyuan 毕竟低学历，只是个自由职业者，真不知道哪来的自信。。。。。

87

laoyuan

2015-07-11 16:14:26 +08:00

@justahappy 毕竟写了8年PHP，这点自信还是有的哇哈哈哈

88

JackWindows

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

好无聊啊，大家都在说生成随机数然后判重
正确姿势难道不是生成一个len(array)的排列，然后按这个序号去访问么？生成排列有线程算法吧

89

sketch33

2015-07-11 16:25:08 +08:00

@laoyuan 为了避免程序遍历整个数组，改为人工遍历整个数组。我怎么就没想到这么好的方法呢？

90

ChangxuBlack

2015-07-11 16:35:18 +08:00

@Septembers 好吧，我以为可以先对数组做预处理呢

91

l12ab

2015-07-11 16:39:32 +08:00

数组转json，然后strpos

92

laoyuan

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

@sketch33 对，人工遍历可以提高系统鲁棒性，比如停电什么的就不怕了

93

jimiton

2015-07-11 16:47:31 +08:00

@laoyuan ...你让我心碎。。。的无以复加

94

kzzhr

2015-07-11 17:09:24 +08:00

转成字符串的本质也是遍历，如果这个也不可以的话，问题就转换成了薛定谔的猫：如何在不查看数组元素的办法猜里面是啥样

95

bramblex

2015-07-11 17:25:45 +08:00

每一种方法都在遍历啊卧槽……

96

BooksE

2015-07-11 17:27:50 +08:00

@procen424 赞同,检查每一个位.不过不知道出题人到底是啥意思

97

latyas

2015-07-11 17:41:36 +08:00

大小都没超过128，7个8bit的数位， 53->00110101
00110101001101010011010100110101001101010011010100110101
XOR 原始数组

如果53在其中，则会有序数为8的整数倍开始的连续的8个0
所以目标是是检测是否有这样的 00000000

对XOR结果的第一第二字节和第四第五字节取AND操作，得到的结果和（11111111第三字节位码）取AND操作，得到一个结果a

if !( a & b0000000011111111) || !(a & b1111111100000000)

则认为53在原始数组中，瞎说的不知道对不对
好像没遍历？

98

wy315700

2015-07-11 17:43:18 +08:00

@sirgod
@laoyuan
不遍历怎么乘起来

99

yiplee

2015-07-11 17:54:38 +08:00

将 Array 转为 Set ,再记下集合里面元素的个数，然后添加 53 进去。如果集合里面元素个数多了一个，那么 53 不在里面；如果保持不变，那么在里面。（我瞎扯的）

100

liuchang0812

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

1

难道没人知道 bloom filter？

1 2

❮

❯