我想到了php中的in_array()函数。但是很明显不对。
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 随机数生成,重复读取判断,这貌似增加复杂度了吧。数组本身无序,已经存在不需要遍历的可能性了吧。要是可接受近似解,貌似有个什么亚线性算法可以用,具体不知了
|
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 --- 好吧,上面开玩笑的,也是遍历,求正确姿势 |
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 构造随机数作为索引随机命中 如果匹配就。。。。。?
|
24
est 2015-07-10 23:14:22 +08:00 1
@Septembers 文字上可以不叫遍历,本质上不也是挨着挨着一个一个问么。
|
28
ning1022 OP @Septembers 这个是个好思路,哈哈!
|
29
dingyaguang117 2015-07-10 23:23:18 +08:00
可以反证 必须要遍历的
|
30
Septembers 2015-07-10 23:27:56 +08:00 via Android
|
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 @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
二分法?
|
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
我觉得需要定义一下遍历。。。
|
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
|
44
ning1022 OP @luoxun 这个用了php内部函数了,我感觉会快些,因为用数字查询比较吧,但是跟in_array()相比也没啥区别!
|
45
sandideas 2015-07-11 00:01:35 +08:00
那个随机数的为什么不直接遍历前6个。。
这样也有七分之一的概率不需要遍历所有。。。 |
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
|
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
要求不遍历,就是二分查找了。二分查找 只有最差的情况才是遍历
排序 已经 遍历了。不遍历根本不能那个排序 |
68
weyou 2015-07-11 13:47:20 +08:00
不让遍历无解, 那是魔术师干的事情。
|
69
weyou 2015-07-11 13:48:53 +08:00
就算是人工一眼看出53在里面, 也包含了目光的遍历。
|
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
排序,二分?
|
76
VicYu 2015-07-11 14:40:29 +08:00
53素数,全乘,摸53,判断是否为0
|
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
|
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)的排列,然后按这个序号去访问么?生成排列有线程算法吧 |
90
ChangxuBlack 2015-07-11 16:35:18 +08:00
@Septembers 好吧,我以为可以先对数组做预处理呢
|
91
l12ab 2015-07-11 16:39:32 +08:00
数组转json,然后strpos
|
94
kzzhr 2015-07-11 17:09:24 +08:00
转成字符串的本质也是遍历,如果这个也不可以的话,问题就转换成了薛定谔的猫:如何在不查看数组元素的办法猜里面是啥样
|
95
bramblex 2015-07-11 17:25:45 +08:00
每一种方法都在遍历啊卧槽……
|
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在原始数组中, 瞎说的 不知道对不对 好像没遍历? |
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?
|