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