【LeetCode】268. Missing Number 解答・解説【Python】

この記事は約2分で読めます。

 

問題

原文

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

 

Example 1:

Example 2:

Example 3:

 

 

内容

[0,n]までの各要素の値が異なる配列numsが与えられます。

配列の中に含まれていない値を返してください。

 

例1:[3,0,1]なら、3個の数字の中で2が含まれていないので2を返します。

例2:[0,1]なら、2個の数字の中で2が含まれていないので2を返します。

例3:[9,6,4,2,3,5,7,0,1]なら、9個の数字の中で8が含まれていないので8を返します。

 

※正しくない可能性があります。

方針

 

解答

解答1:

思いつくままに書いた解答。

“if not i in nums:”の行でnumsに対してiの有無を配列内の全要素に対してチェックしている場合は、時間計算量がO(n^2)になる?

※for節でO(n)、if節でO(n)の探索を行っている?

解答2:二分探索

二分探索の実装はこちらにメモ→二分探索を実装する

配列numsをソート。要素の数だけループを行い、ループ変数が配列numsにあるか二分探索する。

ループ変数iががnumsで見つからなければNoneを返し、Noneが返ってきたらその時のiを返す。

補足・参考・感想

参考

別解:[Python] THE Best explanation, bitwise and sum – Missing Number – LeetCode

 

前:114. Flatten Binary Tree to Linked List

次:704. Binary Search

LeetCode 解答・解説記事一覧

コメント