from collections import defaultdict graph=defaultdict(list) v,e=map(int,input().split()) for i in range(e): u,v=map(str,input().split()) graph[u].append(v) graph[v].append(u) for i in graph: print(i,"->",graph[i]) Input: 7 9 A B A C A F C E C F C D D E D G G F Output: F -> ['A', 'C', 'G'] C -> ['A', 'E', 'F', 'D'] G -> ['D', 'F'] D -> ['C', 'E', 'G'] A -> ['B', 'C', 'F'] E -> ['C', 'D'] B -> ['A']
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