-
Notifications
You must be signed in to change notification settings - Fork 0
/
AdvantageShuffle.py
30 lines (29 loc) · 935 Bytes
/
AdvantageShuffle.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#https://leetcode.com/problems/advantage-shuffle/description/
from collections import defaultdict
class Solution(object):
def advantageCount(self, A, B):
"""
:type A: List[int]
:type B: List[int]
:rtype: List[int]
"""
A_sorted = sorted(A)
B_sorted = sorted(B)
result = defaultdict(list)
no_matches = []
i = 0
end = False
for j in range(len(B)):
if i == len(A):
break
while A_sorted[i] <= B_sorted[j]:
no_matches.append(A_sorted[i])
i += 1
if i == len(A):
end = True
break
if end:
break
result[B_sorted[j]].append(A_sorted[i])
i += 1
return [result[elem].pop() if elem in result and result[elem] else no_matches.pop() for elem in B]