V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
ning1022
V2EX  ›  PHP

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

  •  
  •   ning1022 · 2015-07-10 22:02:34 +08:00 · 11471 次点击
    这是一个创建于 3183 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    119 条回复    2015-07-13 10:50:44 +08:00
    1  2  
    adspe
        1
    adspe  
       2015-07-10 22:07:09 +08:00 via iPad
    用查找算法?
    qiayue
        2
    qiayue  
       2015-07-10 22:09:49 +08:00
    用 implode 合并成逗号分隔的字符串,然后判断字符串?
    任何 php 内部函数都不能用吗还是说仅仅不能用同功能的函数?
    simman
        3
    simman  
       2015-07-10 22:13:31 +08:00
    public static function inArray($item, $array) {
    $flipArray = array_flip($array);
    return isset($flipArray[$item]);
    }

    这个???
    xlmo
        4
    xlmo  
       2015-07-10 22:18:13 +08:00
    不用内部函数?那貌似只能一个一个去if($arr[0] == 53) 了。。
    whahuzhihao
        5
    whahuzhihao  
       2015-07-10 22:20:04 +08:00
    array_flip也是内部函数啊
    iyaozhen
        6
    iyaozhen  
       2015-07-10 22:26:49 +08:00
    应该就是考查找算法吧。
    dallaslu
        7
    dallaslu  
       2015-07-10 22:39:37 +08:00   ❤️ 1
    针对这个数组进行任何处理,都有可能进行遍历的吧!

    如果不需要遍历,不如生成一个 0 到数组长度 -1 随机数,来随机读取数组内元素,每次保证不重复读取相同位置上就行了。这样有七分之一的概率不需要遍历数组。
    br00k
        8
    br00k  
       2015-07-10 22:44:59 +08:00
    不遍历怎么知道??感觉这种问题怎么有点弱智啊。。。
    est
        9
    est  
       2015-07-10 22:45:19 +08:00   ❤️ 1
    赌10元钱任何实现都用到了某种程度上的遍历。
    choury
        10
    choury  
       2015-07-10 22:46:04 +08:00
    不管用什么方法到最后都是要遍历的,至少得知道里面有那些元素吧
    除非能找到一个公式可以生成这个序列,不然不可能的
    lincanbin
        11
    lincanbin  
       2015-07-10 22:51:38 +08:00 via Android
    不让遍历的意思就是不让你逐个看这里面的东西吧。
    PHP内部函数1500个都不让用,又不让看。
    这是什么鬼?
    mouhong
        12
    mouhong  
       2015-07-10 22:51:42 +08:00
    @dallaslu 随机数生成,重复读取判断,这貌似增加复杂度了吧。数组本身无序,已经存在不需要遍历的可能性了吧。要是可接受近似解,貌似有个什么亚线性算法可以用,具体不知了
    loveuqian
        13
    loveuqian  
       2015-07-10 22:52:20 +08:00 via iPhone
    @xlmo 那也是遍历啊
    mouhong
        14
    mouhong  
       2015-07-10 22:53:02 +08:00
    @mouhong 不过这种题感觉就是考个遍历,传说中的 FuzzBuzz 测试
    solupro
        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

    ---
    好吧,上面开玩笑的,也是遍历,求正确姿势
    hobbyliu
        16
    hobbyliu  
       2015-07-10 22:56:33 +08:00
    @dallaslu 此方法,不错,忘记叫什么算法了,概率性很大。
    r00tt
        17
    r00tt  
       2015-07-10 22:59:31 +08:00
    @hobbyliu 是蒙特卡洛么,有点这个的感觉
    hobbyliu
        18
    hobbyliu  
       2015-07-10 23:02:39 +08:00
    @leepood 不是,我记得当初的一个场景时,一个猴子为了排序3个大小不同的干果,不断的往天上抛,直到,排序正确位置,适用于少量元素排序,概率性很大。
    sumhat
        19
    sumhat  
       2015-07-10 23:03:20 +08:00
    $array = {1,22,56,53,34,51,77};

    if (TRUE || array) {
    echo '我灵光一闪,断定 53 必然在这个数组里。';
    }
    101
        20
    101  
       2015-07-10 23:04:48 +08:00
    查找算法也是要遍历的呀
    Septembers
        21
    Septembers  
       2015-07-10 23:11:25 +08:00 via Android
    @est 构造随机数作为索引随机命中 如果匹配就。。。。。?
    ning1022
        22
    ning1022  
    OP
       2015-07-10 23:13:32 +08:00
    @adspe 感觉考察的是算法。但是我不也不会!
    ning1022
        23
    ning1022  
    OP
       2015-07-10 23:14:05 +08:00
    @qiayue 应该是同功能的函数,比如in_array()
    est
        24
    est  
       2015-07-10 23:14:22 +08:00   ❤️ 1
    @Septembers 文字上可以不叫遍历,本质上不也是挨着挨着一个一个问么。
    ning1022
        25
    ning1022  
    OP
       2015-07-10 23:15:24 +08:00
    @simman 我感觉这个不是正确答案!
    ning1022
        26
    ning1022  
    OP
       2015-07-10 23:18:46 +08:00
    @est 我要是面试成功的话,我一定问问他这个答案,我很无语,查了很多资料,感觉是算法。
    ning1022
        27
    ning1022  
    OP
       2015-07-10 23:20:35 +08:00
    @mouhong 大数据算法?感觉有点抽象!
    ning1022
        28
    ning1022  
    OP
       2015-07-10 23:22:57 +08:00
    @Septembers 这个是个好思路,哈哈!
    dingyaguang117
        29
    dingyaguang117  
       2015-07-10 23:23:18 +08:00
    可以反证 必须要遍历的
    Septembers
        30
    Septembers  
       2015-07-10 23:27:56 +08:00 via Android
    hackpro
        31
    hackpro  
       2015-07-10 23:30:57 +08:00
    @dallaslu 正解 某年acm切的題
    如果特別考察你算法的話 翻翻拓撲的東西 以前數學課上過 現在記不清了
    nozama
        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);
    }
    nozama
        33
    nozama  
       2015-07-10 23:35:14 +08:00
    随手写的, 有些typo
    ning1022
        34
    ning1022  
    OP
       2015-07-10 23:37:13 +08:00
    @Septembers 我感觉他考的是效率或者算法。当时我还想到了二叉树,从中间分,log2N。(以前考计算机二级的时候学的,现在都忘了,不知道对不对,呵呵)
    zhaiduo
        35
    zhaiduo  
       2015-07-10 23:39:11 +08:00 via Android
    78
    imyip
        36
    imyip  
       2015-07-10 23:42:34 +08:00 via Android
    二分法?
    ning1022
        37
    ning1022  
    OP
       2015-07-10 23:42:47 +08:00
    @nozama 你这好像没有遍历也没有内部函数,牛呀,但是我得抽空测试下,这个好像是C写的。
    dallaslu
        38
    dallaslu  
       2015-07-10 23:46:15 +08:00
    @ningyuqiao456 如果数组有序,二分还可以
    nozama
        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);
    }
    mulog
        40
    mulog  
       2015-07-10 23:46:40 +08:00
    我觉得需要定义一下遍历。。。
    ning1022
        41
    ning1022  
    OP
       2015-07-10 23:53:27 +08:00
    @nozama 牛,崇拜!
    luoxun
        42
    luoxun  
       2015-07-10 23:54:50 +08:00
    array_flip
    然后 array_key_exists
    应该最快吧 ?
    Hashell
        43
    Hashell  
       2015-07-10 23:58:21 +08:00
    ning1022
        44
    ning1022  
    OP
       2015-07-10 23:59:37 +08:00
    @luoxun 这个用了php内部函数了,我感觉会快些,因为用数字查询比较吧,但是跟in_array()相比也没啥区别!
    sandideas
        45
    sandideas  
       2015-07-11 00:01:35 +08:00
    那个随机数的为什么不直接遍历前6个。。
    这样也有七分之一的概率不需要遍历所有。。。
    ning1022
        46
    ning1022  
    OP
       2015-07-11 00:02:37 +08:00
    @Hashell 这个方法好,我看了,可以,感觉递归有可能是正确答案,但是好像这也是一种遍历!
    luoxun
        47
    luoxun  
       2015-07-11 00:05:33 +08:00
    @sandideas 如果是面试 我觉得 递归和 array_flip 都应该算是正解 起码说得过去
    Felldeadbird
        48
    Felldeadbird  
       2015-07-11 00:16:33 +08:00
    递归算遍历吗?我只想到递归了。
    ghostcat
        49
    ghostcat  
       2015-07-11 00:17:28 +08:00
    以前我面试也被问了这个问题……实在想不出比遍历更快的方法,然后一直不知道答案
    sandideas
        50
    sandideas  
       2015-07-11 00:29:16 +08:00 via iPhone
    @luoxun 基本上就是递归了。。。不过这个的递归想不到什么巧妙的方法。直接简单的递归太没意思了
    sablib
        51
    sablib  
       2015-07-11 00:33:09 +08:00
    请定义 遍历 。。。
    如果说 ·遍历· 是指按照索引顺序的话,那当然是可以做到不用·遍历·。。。
    procen424
        52
    procen424  
       2015-07-11 00:42:43 +08:00 via Android
    如果说遍历是指完整的访问了每一个数,那么对于某些数,只访问其中的一部分二进制位(最少为 1 个位)是不是一种符合条件的解法?
    比如说,用每个数的最低位与待查找数的最低位做位与,相同的挑出来,再比较次低位,以此类推。
    对于这个题来说,如果是 int32 的数组,共 224 个 bit,读取了其中的 44 个 bit 之后确认了 53 的存在,仅仅访问了 19.6% 的数据,是不是不算是严格意义上的遍历呢。
    当然实际情况下你只能按字节读取,即便这样也仅访问了 35.7% 的数据而已。
    然并卵,你硬说它是遍历它确实也是。。。
    Reficul
        53
    Reficul  
       2015-07-11 00:44:50 +08:00 via Android
    递归是遍历的一种方法而已啊,类似遍历二叉树,可以有递归或者非递归的两种算法。这个题目用递归写本质上还是遍历了哇,并且占有内存上还比直接一个个读来的大= =
    feiyuanqiu
        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
    Andiry
        55
    Andiry  
       2015-07-11 01:34:10 +08:00 via Android
    @procen424 思路不错,不过现在CPU cache都是64byte,你读int的一个字节等于读了整个int
    zhangsoledad
        56
    zhangsoledad  
       2015-07-11 02:19:19 +08:00
    不用遍历我也是笑了 这是数组不是hash 面试官傻逼别跟着一帮人 学过数据结构么?
    ChangxuBlack
        57
    ChangxuBlack  
       2015-07-11 02:22:57 +08:00   ❤️ 1
    建议楼主了解一下布隆过滤器
    Septembers
        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#二变量的值存储
    Andiry
        59
    Andiry  
       2015-07-11 06:09:38 +08:00
    @ChangxuBlack 单给你一个数组哪来的bloom filter

    @Septembers 你这个跟遍历没有区别,期望值是一样的
    jesse0628
        60
    jesse0628  
       2015-07-11 06:29:25 +08:00
    hash table 不行?
    proudzhu
        61
    proudzhu  
       2015-07-11 09:33:48 +08:00 via Android
    53 不就在这个数组里吗,一眼就能看出来,实在要写就来个 return array[3] == 53
    yuankui
        62
    yuankui  
       2015-07-11 10:32:21 +08:00
    需求不明,你可以反问面试官几句
    一帮助您正确理解题意
    kn007
        63
    kn007  
       2015-07-11 11:00:02 +08:00
    不可能没有遍历。。。看到有人说递归。。。递归不也是遍历。。。$i++。。
    ant_sz
        64
    ant_sz  
       2015-07-11 11:50:31 +08:00
    我觉得蒙特卡洛算法正解。

    虽然这个算法的期望时间复杂度很高,但是来保证一定可以判断某个数字是否在array里。比如说我们把每次随机生成的下标保存在HashSet里,如果某次随机生成的下标已经在集合里我们就抛弃他。这样经过足够长的时间我们总能100%的确定53是不是在array里。(当集合size和array 的 size 相同的时候结束算法)。
    ant106
        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 算内部函数?
    WispZhan
        66
    WispZhan  
       2015-07-11 12:48:00 +08:00
    要求不遍历,就是二分查找了。二分查找 只有最差的情况才是遍历
    排序 已经 遍历了。不遍历根本不能那个排序
    best1a
        67
    best1a  
       2015-07-11 13:40:48 +08:00
    @ant_sz +1 上面说的递归和字符串啥的,其实都算遍历的一种了
    weyou
        68
    weyou  
       2015-07-11 13:47:20 +08:00
    不让遍历无解, 那是魔术师干的事情。
    weyou
        69
    weyou  
       2015-07-11 13:48:53 +08:00
    就算是人工一眼看出53在里面, 也包含了目光的遍历。
    tushiner
        70
    tushiner  
       2015-07-11 13:58:38 +08:00
    @proudzhu 大亮!
    killerv
        71
    killerv  
       2015-07-11 14:19:29 +08:00
    感觉这个比较问题扯啊,明明是个简单的问题非要复杂化。
    sirgod
        72
    sirgod  
       2015-07-11 14:23:50 +08:00
    注意到53是素数所以全部乘起来再模53看是否等于0就好了
    myywin
        73
    myywin  
       2015-07-11 14:25:20 +08:00
    排序,二分?
    laoyuan
        74
    laoyuan  
       2015-07-11 14:26:04 +08:00
    @sirgod 终于出现正确答案了。
    013231
        75
    013231  
       2015-07-11 14:34:17 +08:00
    @sirgod
    @laoyuan
    你们打算怎样把数组全部乘起来?
    VicYu
        76
    VicYu  
       2015-07-11 14:40:29 +08:00
    53素数,全乘,摸53,判断是否为0
    jimiton
        77
    jimiton  
       2015-07-11 14:40:42 +08:00
    @sirgod
    全部乘起来,不是得遍历一遍,取出数字相乘么?
    相比较遍历一遍,取数比较,有什么优势
    znoodl
        78
    znoodl  
       2015-07-11 14:43:48 +08:00 via iPad
    @sirgod
    @laoyuan
    本来遍历到一半就能确认的问题,非要遍历一遍算积再除
    sketch33
        79
    sketch33  
       2015-07-11 14:45:28 +08:00
    笑死人了,还tm正确答案,真不知道是不是高级黑……
    sketch33
        80
    sketch33  
       2015-07-11 14:47:17 +08:00
    这个肯定要遍历的啊,就算完全不懂编程好了,假设里面100个元素,使用某种手段访问了其中99个,发现没找到这个数字,那么剩下那个数字你是访问呢还是不访问呢
    Clarencep
        81
    Clarencep  
       2015-07-11 15:02:34 +08:00   ❤️ 1
    遇到这种公司,直接拜拜是最好的选择;要是进去了,还不知道会遇到什么213的产品经理呢,到那时就欲哭无泪了。
    kurtis
        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。
    laoyuan
        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));

    完美解决!
    laoyuan
        84
    laoyuan  
       2015-07-11 15:46:25 +08:00
    看那乘积,果然是大数据!
    hooluupog
        85
    hooluupog  
       2015-07-11 15:57:21 +08:00
    一般面试考这类东西都是考算法的。
    所以这个题十有八九是让你给出一个时间复杂度小于O(n)的算法来找出某个元素。
    有序数组,直接2分查找;
    部分有序或者是循环有序数组,也是采用划分的思想,不过需要确定单调区间来决定每次查找的区间。
    楼主给的这个数组感觉有问题啊。
    justahappy
        86
    justahappy  
       2015-07-11 16:08:53 +08:00
    @laoyuan 毕竟低学历,只是个自由职业者,真不知道哪来的自信。。。。。
    laoyuan
        87
    laoyuan  
       2015-07-11 16:14:26 +08:00
    @justahappy 毕竟写了8年PHP,这点自信还是有的哇哈哈哈
    JackWindows
        88
    JackWindows  
       2015-07-11 16:20:35 +08:00
    好无聊啊,大家都在说生成随机数然后判重
    正确姿势难道不是生成一个len(array)的排列,然后按这个序号去访问么?生成排列有线程算法吧
    sketch33
        89
    sketch33  
       2015-07-11 16:25:08 +08:00
    @laoyuan 为了避免程序遍历整个数组,改为人工遍历整个数组。我怎么就没想到这么好的方法呢?
    ChangxuBlack
        90
    ChangxuBlack  
       2015-07-11 16:35:18 +08:00
    @Septembers 好吧,我以为可以先对数组做预处理呢
    l12ab
        91
    l12ab  
       2015-07-11 16:39:32 +08:00
    数组转json,然后strpos
    laoyuan
        92
    laoyuan  
       2015-07-11 16:47:16 +08:00
    @sketch33 对,人工遍历可以提高系统鲁棒性,比如停电什么的就不怕了
    jimiton
        93
    jimiton  
       2015-07-11 16:47:31 +08:00
    @laoyuan ...你让我心碎。。。的无以复加
    kzzhr
        94
    kzzhr  
       2015-07-11 17:09:24 +08:00
    转成字符串的本质也是遍历,如果这个也不可以的话,问题就转换成了薛定谔的猫:如何在不查看数组元素的办法猜里面是啥样
    bramblex
        95
    bramblex  
       2015-07-11 17:25:45 +08:00
    每一种方法都在遍历啊卧槽……
    BooksE
        96
    BooksE  
       2015-07-11 17:27:50 +08:00
    @procen424 赞同,检查每一个位.不过不知道出题人到底是啥意思
    latyas
        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在原始数组中, 瞎说的 不知道对不对
    好像没遍历?
    wy315700
        98
    wy315700  
       2015-07-11 17:43:18 +08:00
    @sirgod
    @laoyuan
    不遍历怎么乘起来
    yiplee
        99
    yiplee  
       2015-07-11 17:54:38 +08:00
    将 Array 转为 Set ,再记下集合里面元素的个数,然后添加 53 进去。如果集合里面元素个数多了一个,那么 53 不在里面;如果保持不变,那么在里面。(我瞎扯的)
    liuchang0812
        100
    liuchang0812  
       2015-07-11 19:11:19 +08:00   ❤️ 1
    难道没人知道 bloom filter?
    1  2  
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5490 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 35ms · UTC 08:24 · PVG 16:24 · LAX 01:24 · JFK 04:24
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.