問(wèn)題描述

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

問(wèn)題解答

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

另建一個(gè)長(zhǎng)度為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)

我回答過(guò)的問(wèn)題: Python-QA