Repeat and Missing Number Array Asked in: Amazon
You are given a read-only array of n integers from 1 to n.
Each integer appears exactly once except A which appears twice and B which is missing.
Return A and B.
Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Note that in your output A should precede B.
Example:
Input:[3 1 2 5 3]
Output:[3, 4]
A = 3, B = 4
Solution:
class Solution:
# @param A : tuple of integers
# @return a list of integers
def repeatedNumber(self, A):
d={}
for i in A:
if i in d:
d[i]+=1
else:
d[i]=1
for i in range(1,len(A)+1):
if i not in d:
d[i]=0
return [max(d,key=lambda x:d[x]),min(d,key=lambda x:d[x])]
Screenshot :
Comments
Post a Comment