問題
原文
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
コメント