C++ Py3 計數排序與partial sum解Leetcode 2300 Successful Pairs of Spells and ...

C++ Py3  計數排序與partial sum解Leetcode 2300  Successful Pairs of Spells and Potions

Portions的極大值小於等於10萬是可進行記數排序的關鍵，既然可以採用記數排序，後面的二元搜尋也可以透過partial sum的手法加速。

[Py3 code請進]

------

The key to performing count sorting is that the maximum value of Portions is less than or equal to 100,000. Since count sorting can be used, the subsequent binary search can  be removed & accelerated through the partial sum technique.

[codes on Leetcode]https://leetcode.com/problems/successful-pairs-of-spells-and-potions/solutions/7257556/counting-sort-then-binary-search-vs-linear-3ms-beats-99-20/

[Prefix Sum playlist]https://www.youtube.com/watch?v=1kA_aZHewmU&list=PLYRlUBnWnd5LkYN-5ptHDrtPXOuHm9uSq

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        freq=Counter(potions)
        pMax=max(freq)
        F=[0]*(1+pMax)
        for p, f in freq.items():
            F[p]=f
        freq=list(accumulate(F))
        n, m=len(spells), len(potions)
        res=[0]*n
        for i, x in enumerate(spells):
            k=(success+x-1)//x
            if k lt;=pMax:
                res[i]=m-freq[k-1]
        return res