問題描述

面試題：定義一個數(shù)組長度是49，在里邊隨機放入1到50中的49個，設(shè)計一種最快的算法，求出那個數(shù)沒被放入。

問題解答

求1到50的和，然后遍歷數(shù)組求和，相減，如何

另建一個長度為50的數(shù)組，全部初始化為0，遍歷給定數(shù)組，置新建數(shù)組下標(biāo)等于給定數(shù)組當(dāng)前值的位置為1，最后輸出新建數(shù)組值為0的下標(biāo)。這是我的第一反應(yīng)，坐等更好的辦法。

用 1 到 50 的和去扣掉所有在數(shù)組中的數(shù)字:

# array is an array with length 49ans = 1275for 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