这是一个创建于 2426 天前的主题，其中的信息可能已经有所发展或是发生改变。
1.一个整数数组，求这个整数数组中哪两个数相加等于 100，写出算法（假设数组中没有重复值，无序）。
我首先想到的是穷举，但是时间复杂度太高，pass，然后能想到的就是用 100 依次减去数组中的整数，然后再判断一下差值是否在数组中，但是面试官说还是没达到他的要求，我暂时没想出来
2.求 100 的阶乘
我能想到的就是迭代和递归两种方式，递归我知道肯定是跑不了的，跑完估计几百年以后了。迭代的话结果数字又太大，没有类型能存下，面试官问有没有更好的办法，我暂时没想出来
平时算法接触的不多，没想过这些问题，求各位提供一下思路，好让我开悟
-----------------一个正在找工作的苦逼 PHP 程序员
 |
1
BlackGlory 2018-05-03 20:56:10 +08:00  1
1. 先排序, 从首项和尾项开始搜索.
2. 用数组模拟大数, 手动实现小学乘法. |
 |
2
lalala121 OP @BlackGlory 排序不是先要来一遍 O(logN)吗？搜索又来一遍 O(N),面试官说最多跑一遍就要找到
|
|
3
lalala121 OP @BlackGlory 第二题面试官给我的意思是，有比迭代时间复杂度更低的算法，所以我跳出了递归和迭代想第三种算法去了，数组模拟那个，我回来上网搜索也看到了，我想知道有没有比迭代时间复杂度更低的算法，还是我想多了
|
 |
4
eccstartup 2018-05-03 21:13:59 +08:00 via iPhone
后面的搜索是二分法
|
 |
5
WispZhan 2018-05-03 21:14:54 +08:00 via Android
第二题是数学问题
|
 |
6
goreliu 2018-05-03 21:22:50 +08:00 via Android 3
第一题，准备一个哈希表，把每个数作为键值为 1 存进去，然后遍历一次数组，在哈希表里一次检查 100 - num 是否存在。
|
 |
7
takato 2018-05-03 21:24:54 +08:00 1
第二题可以参考一下这个：
http://www.matrix67.com/blog/archives/393 |
|
8
goreliu 2018-05-03 21:25:12 +08:00 via Android
#6 一次 - 依次。另外如果没有负数的话，用 int[100] 数组就可以了。
|
|
11
BlackGlory 2018-05-03 21:30:21 +08:00
@lalala121 直接桶排序也可以, 基本不需要时间.
|
 |
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.感觉应该是大数乘法吧。难不成要上斯特林公式？ |
|
13
lalala121 OP @BlackGlory 了解了，谢谢
|
|
14
goreliu 2018-05-03 21:35:34 +08:00 via Android 1
@lalala121 #9 重点看怎么检查的。如果有负数，范围允许的话，也可以开两个大数组，一个存正数，一个存负数。
|
|
15
BlackGlory 2018-05-03 21:36:44 +08:00
第二题其实还可以动态规划
|
 |
17
carlclone 2018-05-03 22:02:25 +08:00
@lalala121 他说的是哈希表 , 标记数组法 , 把数值存为数组的 key , 不是 value , 查找是 O(1)复杂度 , 遍历是 O(n) 总的 O(n)
|
|
18
carlclone 2018-05-03 22:04:51 +08:00 1
第二题类似斐波那契 , 递归 +记忆化搜索 , 或直接动态规划
|
 |
19
guokeke 2018-05-03 22:06:50 +08:00 via Android 2
第一个问题。让每个数减 50。绝对值相等的数陪睡。
|
 |
20
Hosuke 2018-05-03 22:13:02 +08:00 1
第一题在你的思路的基础上加个布隆过滤器快速判断差值是否存在数组中
第二题只想到高精度乘法，数组乘以 int |
 |
21
stevenbipt 2018-05-03 22:13:23 +08:00 1
第一个用哈希表就很快了，如果没记错就是 leetcode 的第一个题，第二题不太清楚
|
 |
22
enenaaa 2018-05-03 22:20:33 +08:00 1
第一题， 楼主的解法， 后面检查那步如果是遍历的话， 复杂度是 O(n^2)。先排序再对向搜索， 复杂度是 O(nlogn + n)。记得 leetcode 上有这题。
第二题， 用动态规划。 |
 |
23
iugo 2018-05-03 22:24:14 +08:00 1
|
|
24
stevenbipt 2018-05-03 22:36:53 +08:00 1
第二题想了一下可能用分治法把 4 个数分为一组先进行相乘转化成科学记数法的形式，然后对每一组的数字进行乘法，10 的次方数进行相加，不过需要处理的是小数乘的时候的精度，如果能保持精度说不定能行
|
|
25
enenaaa 2018-05-03 23:31:33 +08:00
sorry, 第二题没仔细看题目。阶乘无法直接用动态规划解决。
|
 |
26
nl101531 2018-05-03 23:44:26 +08:00 via Android
第一题不是 leetcode 的第一题吗？
|
 |
27
Daath 2018-05-04 00:00:02 +08:00 via Android
第一道我能想到就是，遍历一次整数数组，把值都当做另外个字典的 key，其然后 value 加 1，初始值为 0，然后判断 100-值的差值作为字典 key 来查 value 大于 0，如果有就凑一对 print 出来。
|
|
28
Daath 2018-05-04 00:01:41 +08:00 via Android
当年毕业面试的时候也遇到跟这个很类似的，就只是单单问时间复杂度最小是多少
|
 |
29
heiybb 2018-05-04 07:52:25 +08:00
记得以前在 EXCEL 里碰到过 多个值求与目标值最相近的子集和
|
 |
30
melissa104 2018-05-04 09:14:51 +08:00
感觉用 js 好容易弄哦。。。
|
 |
31
larendorrx 2018-05-04 09:39:56 +08:00 via Android
@stevenbipt 是的，就是 leetcode 上的，用 hash 缓存 100-x
|
 |
32
cgsv 2018-05-04 09:58:06 +08:00
额，这些算是最基本的算法题了吧。另外求 100 的阶乘迭代和递归时间复杂度是一样的，这个不是 fibonacci 数列，递归过程没有重复的计算
|
|
34
stevenbipt 2018-05-04 12:03:53 +08:00 via Android
如果不考虑了具体精度只需要知道大概的数量级可以直接转化成 log 以 10 为底数的的和，最后出来的结果就是 10 的指数
|
 |
35
earendil1412 2018-05-04 12:25:42 +08:00 via Android
第一题能快过 O(n)?
第二题楼主怕不是对递归和空间复杂度有什么误解 |
|
36
lalala121 OP @earendil1412 不知道啊，我回家用递归和迭代试了，迭代的结果转成科学计数法输出了，递归直接报错了，php 实现的
|
|
37
lalala121 OP @earendil1412 额，不好意思，可能是我搞错了，又试了一下，递归是可以运行的，抱歉
|
 |
38
hackpro 2018-05-08 09:23:43 +08:00
第一题可以用桶 一个数一个坑 给定一个数 i 检查 100-i 在不在坑里就知道了
缺点是如果这题把 100 改成 100W 这方法就挂了 |
 |
39
LenonZeng 2018-05-17 21:42:49 +08:00 1
100 以内不重复两个整数相加，只有 50 对 （ 0，100 ）（ 1, 99 ）（ 2，98 ）...（ 49，51 ）；将数组的值映射到位图，位图大小为最大整数值；然后，检查这 50 个对应的位的值都为 1，结果就是存在。理论只有检查 50 次，其他都是数据输入的时间。当然前提是都是正整数。
|
Select Language