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

面试遇到的两个算法题

  •  1
     
  •   lalala121 · 2018-05-03 20:46:55 +08:00 · 5226 次点击
    这是一个创建于 2156 天前的主题,其中的信息可能已经有所发展或是发生改变。

    1.一个整数数组,求这个整数数组中哪两个数相加等于 100,写出算法(假设数组中没有重复值,无序)。

    我首先想到的是穷举,但是时间复杂度太高,pass,然后能想到的就是用 100 依次减去数组中的整数,然后再判断一下差值是否在数组中,但是面试官说还是没达到他的要求,我暂时没想出来

    2.求 100 的阶乘

    我能想到的就是迭代和递归两种方式,递归我知道肯定是跑不了的,跑完估计几百年以后了。迭代的话结果数字又太大,没有类型能存下,面试官问有没有更好的办法,我暂时没想出来

    平时算法接触的不多,没想过这些问题,求各位提供一下思路,好让我开悟

    -----------------一个正在找工作的苦逼 PHP 程序员

    39 条回复    2018-05-17 21:42:49 +08:00
    BlackGlory
        1
    BlackGlory  
       2018-05-03 20:56:10 +08:00   ❤️ 1
    1. 先排序, 从首项和尾项开始搜索.
    2. 用数组模拟大数, 手动实现小学乘法.
    lalala121
        2
    lalala121  
    OP
       2018-05-03 21:10:22 +08:00
    @BlackGlory 排序不是先要来一遍 O(logN)吗?搜索又来一遍 O(N),面试官说最多跑一遍就要找到
    lalala121
        3
    lalala121  
    OP
       2018-05-03 21:12:34 +08:00
    @BlackGlory 第二题面试官给我的意思是,有比迭代时间复杂度更低的算法,所以我跳出了递归和迭代想第三种算法去了,数组模拟那个,我回来上网搜索也看到了,我想知道有没有比迭代时间复杂度更低的算法,还是我想多了
    eccstartup
        4
    eccstartup  
       2018-05-03 21:13:59 +08:00 via iPhone
    后面的搜索是二分法
    WispZhan
        5
    WispZhan  
       2018-05-03 21:14:54 +08:00 via Android
    第二题是数学问题
    goreliu
        6
    goreliu  
       2018-05-03 21:22:50 +08:00 via Android   ❤️ 3
    第一题,准备一个哈希表,把每个数作为键值为 1 存进去,然后遍历一次数组,在哈希表里一次检查 100 - num 是否存在。
    takato
        7
    takato  
       2018-05-03 21:24:54 +08:00   ❤️ 1
    第二题可以参考一下这个:
    http://www.matrix67.com/blog/archives/393
    goreliu
        8
    goreliu  
       2018-05-03 21:25:12 +08:00 via Android
    #6 一次 - 依次。另外如果没有负数的话,用 int[100] 数组就可以了。
    lalala121
        9
    lalala121  
    OP
       2018-05-03 21:25:23 +08:00
    @goreliu 你这个方法我说了,面试官说,你每次都检查一次也要耗费一定时间,给我否了
    lalala121
        10
    lalala121  
    OP
       2018-05-03 21:26:06 +08:00
    @takato 谢谢
    BlackGlory
        11
    BlackGlory  
       2018-05-03 21:30:21 +08:00
    @lalala121 直接桶排序也可以, 基本不需要时间.
    saluton
        12
    saluton  
       2018-05-03 21:30:43 +08:00
    1、每个数大小都在 [1, 100] 的话,直接开一个长度的数组 tmp,
    tmp[a] = index,表示原始数据中值为 a 的在 index 处。

    遍历题目这个数组
    判断 tmp[100 - A[index]] 是否为空,同时标记 tmp[A[index]] = index

    每个数大小不定的话,直接开个 set 扫一边吧

    2.感觉应该是大数乘法吧。难不成要上斯特林公式?
    lalala121
        13
    lalala121  
    OP
       2018-05-03 21:34:17 +08:00
    @BlackGlory 了解了,谢谢
    goreliu
        14
    goreliu  
       2018-05-03 21:35:34 +08:00 via Android   ❤️ 1
    @lalala121 #9 重点看怎么检查的。如果有负数,范围允许的话,也可以开两个大数组,一个存正数,一个存负数。
    BlackGlory
        15
    BlackGlory  
       2018-05-03 21:36:44 +08:00
    第二题其实还可以动态规划
    lalala121
        16
    lalala121  
    OP
       2018-05-03 21:41:51 +08:00
    @goreliu 谢谢
    carlclone
        17
    carlclone  
       2018-05-03 22:02:25 +08:00
    @lalala121 他说的是哈希表 , 标记数组法 , 把数值存为数组的 key , 不是 value , 查找是 O(1)复杂度 , 遍历是 O(n) 总的 O(n)
    carlclone
        18
    carlclone  
       2018-05-03 22:04:51 +08:00   ❤️ 1
    第二题类似斐波那契 , 递归 +记忆化搜索 , 或直接动态规划
    guokeke
        19
    guokeke  
       2018-05-03 22:06:50 +08:00 via Android   ❤️ 2
    第一个问题。让每个数减 50。绝对值相等的数陪睡。
    Hosuke
        20
    Hosuke  
       2018-05-03 22:13:02 +08:00   ❤️ 1
    第一题在你的思路的基础上加个布隆过滤器快速判断差值是否存在数组中
    第二题只想到高精度乘法,数组乘以 int
    stevenbipt
        21
    stevenbipt  
       2018-05-03 22:13:23 +08:00   ❤️ 1
    第一个用哈希表就很快了,如果没记错就是 leetcode 的第一个题,第二题不太清楚
    enenaaa
        22
    enenaaa  
       2018-05-03 22:20:33 +08:00   ❤️ 1
    第一题, 楼主的解法, 后面检查那步如果是遍历的话, 复杂度是 O(n^2)。先排序再对向搜索, 复杂度是 O(nlogn + n)。记得 leetcode 上有这题。

    第二题, 用动态规划。
    iugo
        23
    iugo  
       2018-05-03 22:24:14 +08:00   ❤️ 1
    stevenbipt
        24
    stevenbipt  
       2018-05-03 22:36:53 +08:00   ❤️ 1
    第二题想了一下可能用分治法把 4 个数分为一组先进行相乘转化成科学记数法的形式,然后对每一组的数字进行乘法,10 的次方数进行相加,不过需要处理的是小数乘的时候的精度,如果能保持精度说不定能行
    enenaaa
        25
    enenaaa  
       2018-05-03 23:31:33 +08:00
    sorry, 第二题没仔细看题目。阶乘无法直接用动态规划解决。
    nl101531
        26
    nl101531  
       2018-05-03 23:44:26 +08:00 via Android
    第一题不是 leetcode 的第一题吗?
    Daath
        27
    Daath  
       2018-05-04 00:00:02 +08:00 via Android
    第一道我能想到就是,遍历一次整数数组,把值都当做另外个字典的 key,其然后 value 加 1,初始值为 0,然后判断 100-值的差值作为字典 key 来查 value 大于 0,如果有就凑一对 print 出来。
    Daath
        28
    Daath  
       2018-05-04 00:01:41 +08:00 via Android
    当年毕业面试的时候也遇到跟这个很类似的,就只是单单问时间复杂度最小是多少
    heiybb
        29
    heiybb  
       2018-05-04 07:52:25 +08:00
    记得以前在 EXCEL 里碰到过 多个值求与目标值最相近的子集和
    melissa104
        30
    melissa104  
       2018-05-04 09:14:51 +08:00
    感觉用 js 好容易弄哦。。。
    larendorrx
        31
    larendorrx  
       2018-05-04 09:39:56 +08:00 via Android
    @stevenbipt 是的,就是 leetcode 上的,用 hash 缓存 100-x
    cgsv
        32
    cgsv  
       2018-05-04 09:58:06 +08:00
    额,这些算是最基本的算法题了吧。另外求 100 的阶乘迭代和递归时间复杂度是一样的,这个不是 fibonacci 数列,递归过程没有重复的计算
    lalala121
        33
    lalala121  
    OP
       2018-05-04 10:48:06 +08:00
    @cgsv 但是实际情况是,递归根本跑不完 100 的阶乘,写成递归完全没法用,空间复杂度太高了
    stevenbipt
        34
    stevenbipt  
       2018-05-04 12:03:53 +08:00 via Android
    如果不考虑了具体精度只需要知道大概的数量级可以直接转化成 log 以 10 为底数的的和,最后出来的结果就是 10 的指数
    earendil1412
        35
    earendil1412  
       2018-05-04 12:25:42 +08:00 via Android
    第一题能快过 O(n)?
    第二题楼主怕不是对递归和空间复杂度有什么误解
    lalala121
        36
    lalala121  
    OP
       2018-05-04 12:33:31 +08:00
    @earendil1412 不知道啊,我回家用递归和迭代试了,迭代的结果转成科学计数法输出了,递归直接报错了,php 实现的
    lalala121
        37
    lalala121  
    OP
       2018-05-04 12:39:41 +08:00
    @earendil1412 额,不好意思,可能是我搞错了,又试了一下,递归是可以运行的,抱歉
    hackpro
        38
    hackpro  
       2018-05-08 09:23:43 +08:00
    第一题可以用桶 一个数一个坑 给定一个数 i 检查 100-i 在不在坑里就知道了
    缺点是如果这题把 100 改成 100W 这方法就挂了
    LenonZeng
        39
    LenonZeng  
       2018-05-17 21:42:49 +08:00   ❤️ 1
    100 以内不重复两个整数相加,只有 50 对 ( 0,100 )( 1, 99 )( 2,98 )...( 49,51 );将数组的值映射到位图,位图大小为最大整数值;然后,检查这 50 个对应的位的值都为 1,结果就是存在。理论只有检查 50 次,其他都是数据输入的时间。当然前提是都是正整数。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3381 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 13:16 · PVG 21:16 · LAX 06:16 · JFK 09:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.