はじめに
LeetCodeの問題を解答します。
なるべく、問題の和訳と詳細なコメントを書いています。
余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。
様々なカテゴリの問題をランダムにあたる方法も良いですが、
二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。
テーマごとに問題を分類しました。
LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。
また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。
LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。
はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。
問題
原文
Given an array
numscontainingndistinct 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：
|
1 2 3 4 5 6 7 8 |
class Solution: def missingNumber(self, nums: List[int]) -> int: nums.sort() length = len(nums) for i in range(1,length+1): if not i in nums: return i return 0 |
思いつくままに書いた解答。
“if not i in nums:”の行でnumsに対してiの有無を配列内の全要素に対してチェックしている場合は、時間計算量がO(n^2)になる？
※for節でO(n)、if節でO(n)の探索を行っている？
解答2：二分探索
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution: def binary_search(self, nums, target): min = 0 max = len(nums)-1 while min <= max: middle = (min+max)//2 if target==nums[middle]: return middle elif target<nums[middle]: max = middle - 1 else: min = middle + 1 return None def missingNumber(self, nums: List[int]) -> int: nums.sort() length = len(nums) for i in range(1,length+1): if self.binary_search(nums, i) is None: return i return 0 |
二分探索の実装はこちらにメモ→二分探索を実装する
配列numsをソート。要素の数だけループを行い、ループ変数が配列numsにあるか二分探索する。
ループ変数iががnumsで見つからなければNoneを返し、Noneが返ってきたらその時のiを返す。
補足・参考・感想
参考
別解：[Python] THE Best explanation, bitwise and sum – Missing Number – LeetCode
コメント