I am trying to use hash table to solve this question. The question description is: "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."
My approach so far is to import the dictionary and use it as a list. Then I am enumerating through the integer array that is given to me. So, for now, nums=[0,1,2,3,4,6]. I have to return number 5 as the missing number. After enumerating, I am trying to go over the items of the dictionary and see which number is missing. If the length of the v is none inside the index, then I will return this line int((((length * (length 1))/2) - sums))
from collections import defaultdict
class Solution(object):
def missingNumber(self, nums):
d = defaultdict(list)
length = len(nums)
sums = sum(nums)
for numbers, index in enumerate(nums):
d[index].append(numbers)
for k,v in d.items():
if len(v) == 0 :
return int((((length * (length 1))/2) - sums))
I am confused about how to show the if statement. Like how from the list it can be recognized that 5 is missing. Also, if there are more than 2 numbers are missing, then what approach will be the best to take? As if the example was: nums = [0,1,2,6,8]
Pardon for not having enough knowledge. I am just a beginner trying to practice questions everyday.
CodePudding user response:
If you can use sum
then no loop is required:
sum1 = sum(nums)
sum2 = sum(range(n))
missing_num = sum2 - sum1
CodePudding user response:
You don't need a dict, you can do it in a for loop
for i in range(n)
if i not in nums:
return i
if you are not told what n
is then you can do something like:
for i in range(nums[-1])
if i not in nums:
return i
if there are a possibility of more than one number missing then you can add them to a list before returning them
missing_nums = []
for i in range(nums[-1]):
if i not in nums:
missing_nums.append(i)
return missing_nums