java - 面试题：定义一个数组长度是49，在里边随机放入1到50中的49个，设计一种最快的算法，求出那个数没被放入。

Question

面试题：定义一个数组长度是49，在里边随机放入1到50中的49个，设计一种最快的算法，求出那个数没被放入。

Answer 1

求1到50的和，然后遍历数组求和，相减，如何

Answer 2

另建一个长度为50的数组，全部初始化为0，遍历给定数组，置新建数组下标等于给定数组当前值的位置为1，最后输出新建数组值为0的下标。这是我的第一反应，坐等更好的办法。

Answer 3

用 1 到 50 的和去扣掉所有在数组中的数字:

# array is an array with length 49

ans = 1275

for i in range(49):
    ans -= array[i]
    
# ans is the number we want to find

Time Complexity: O(n)
Space Complexity: O(1)

---

我回答过的问题: Python-QA