870. Advantage Shuffle

Given two arrays A and B of equal size, the advantage of A with respect to B is the number of indices i for which A[i] > B[i].

Return any permutation of A that maximizes its advantage with respect to B.

Example 1:
Input: A = [2,7,11,15], B = [1,10,4,11]
Output: [2,11,7,15]

Example 2:
Input: A = [12,24,8,32], B = [13,25,32,11]
Output: [24,32,8,12]

Note:
1 <= A.length = B.length <= 10000
0 <= A[i] <= 10^9
0 <= B[i] <= 10^9

Solution:

class Solution:
    def advantageCount(self, A: List[int], B: List[int]) -> List[int]:
        a = sorted(A)
        b = sorted(B)
        match = defaultdict(list)
        no_match = []
        j = 0
        for i in range(len(a)):
            if a[i] > b[j]:
                match[b[j]].append(a[i])
                j += 1
            else:
                no_match.append(a[i])
        # either return matched b value or non matched a value
        return [match[i].pop() if i in match and len(match[i])>0 else no_match.pop() for i in B]

references

https://leetcode.com/problems/advantage-shuffle/

# leetcode challenge, medium, python

Commentaires

Articles

73

Catégories

11

870. Advantage Shuffle

references

Commentaires

Catégories

Nuage de tags

Récents

Archives

Récents

Archives

Your browser is out-of-date!