面试遇到的两个算法题

[lalala121]

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

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

2.求 100 的阶乘

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

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

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

[BlackGlory]

1. 先排序, 从首项和尾项开始搜索.
2. 用数组模拟大数, 手动实现小学乘法.

[lalala121]

@BlackGlory 排序不是先要来一遍 O(logN)吗？搜索又来一遍 O(N),面试官说最多跑一遍就要找到

[lalala121]

@BlackGlory 第二题面试官给我的意思是，有比迭代时间复杂度更低的算法，所以我跳出了递归和迭代想第三种算法去了，数组模拟那个，我回来上网搜索也看到了，我想知道有没有比迭代时间复杂度更低的算法，还是我想多了

[eccstartup]

后面的搜索是二分法

[WispZhan]

第二题是数学问题

[goreliu]

第一题，准备一个哈希表，把每个数作为键值为 1 存进去，然后遍历一次数组，在哈希表里一次检查 100 - num 是否存在。

[takato]

第二题可以参考一下这个：
http://www.matrix67.com/blog/archives/393

[goreliu]

#6 一次 - 依次。另外如果没有负数的话，用 int[100] 数组就可以了。

[lalala121]

@goreliu 你这个方法我说了，面试官说，你每次都检查一次也要耗费一定时间，给我否了

[lalala121]

@takato 谢谢

[BlackGlory]

@lalala121 直接桶排序也可以, 基本不需要时间.

[saluton]

1、每个数大小都在 [1, 100] 的话，直接开一个长度的数组 tmp，
tmp[a] = index，表示原始数据中值为 a 的在 index 处。

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

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

2.感觉应该是大数乘法吧。难不成要上斯特林公式？

[lalala121]

@BlackGlory 了解了，谢谢

[goreliu]

@lalala121 #9 重点看怎么检查的。如果有负数，范围允许的话，也可以开两个大数组，一个存正数，一个存负数。

[BlackGlory]

第二题其实还可以动态规划

[lalala121]

@goreliu 谢谢

[carlclone]

@lalala121 他说的是哈希表 , 标记数组法 , 把数值存为数组的 key , 不是 value , 查找是 O(1)复杂度 , 遍历是 O(n) 总的 O(n)

[carlclone]

第二题类似斐波那契 , 递归 +记忆化搜索 , 或直接动态规划

[guokeke]

第一个问题。让每个数减 50。绝对值相等的数陪睡。

[Hosuke]

第一题在你的思路的基础上加个布隆过滤器快速判断差值是否存在数组中
第二题只想到高精度乘法，数组乘以 int