問題
原文
Given an array
nums
containingn
distinct numbers in the range[0, n]
, return the only number in the range that is missing from the array.
Example 1:
123 Input: nums = [3,0,1]Output: 2Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.Example 2:
123 Input: nums = [0,1]Output: 2Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.Example 3:
123 Input: nums = [9,6,4,2,3,5,7,0,1]Output: 8Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.
内容
[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
コメント