leetcode 2300. Successful Pairs of Spells and Potions（排序 / 桶排序 + BS）

spells数组里面装的是法术，potions数组里面装的是药水。
spells[i] * potions[j] >= success就算成功配对，
返回一个数组res, res[i ] 是spells[i]和potions数组里配对的个数。

思路：

最粗暴的办法，每个spells[i]依次和所有potions[j]相乘，找出所有匹配的个数。
不用想，肯定TLE。

那换个方法，先把potions升序排序，用success / potions就得到想要的目标spells。

spells[i] >= 目标spells时就会满足spells[i] * potions[j] >= success,
因为目标spells是降序排列的，
只要找到第一个spells[i] >= 目标spells[j]，那 j 后面的都会>=, 总个数就是m - j;

如果线性搜索 j ，也会TLE， 因为最坏的情况是O(mn).

那么换binary search搜索呢, 就不能用降序排列，因为BS要求升序。

而且不能用java自带的binary search, 因为会有重复的元素存在，
而java中也说明了，如果有重复元素存在，不确定返回的是哪个。

实现binary search的思路是，如果满足spells[i] * potions[mid] >= success,
说明potions[mid] 还可以再小一点，
于是right = mid (不要=mid-1, 不然如果正好==success, potions[mid]可能会被错过)。
另外初始right = m, 而不是m-1,
因为最后res[i] = m-左边界left 是可以等于0的（没有匹配），意味着左边界left最后可以= m。
（用[1,2,3,4,5,6,7]试下）

涉及排序，所以时间复杂度是O(nlogn)。

    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int n = spells.length;
        int m = potions.length;
        int[] res = new int[n];

        Arrays.sort(potions);
       
        for(int i = 0; i < n; i++) {
            int left = 0;
            int right = m;

            while(left < right) {
                int mid = left + (right - left)/2;
               
                if((long)spells[i] * potions[mid] >= success) right = mid;
                else left = mid+1;
            }
            res[i] += m - left;
            
        }
        
        return res;
    }

还有一种更快的方法，时间复杂度是O(n)。

也是binary search, 不过它不给potions排序。

要统计个数，不要忘了桶排序的思想。只要找到了桶，就找到了对应的个数。

记下每个potion出现的次数。不想占用那么大的空间，就记下最大值。
然后对每个spells[ i ], 找到一个最小的potion, 满足spells[i] * potion >= success。
那么排好序的potions（桶的下标）中>=potion的（potion右边的）都满足。

而事先把所有>=potion出现的次数都统计好，存在数组potionCnt,
取potionCnt[ potion] 就得到想要的结果。

potion就不从potions[0]开始找了，直接从最近的success / spells[i]开始，
不满足条件就+1.
如果一开始目标success / spells[i]就比potion的最大值还大，说明没有满足条件的potion, 跳过。

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int n = spells.length;
        int m = potions.length;
        int[] res = new int[n];
        int maxPotion = 0;

        for(int potion : potions) maxPotion = Math.max(potion, maxPotion);

        int[] potionCnt = new int[maxPotion+1];
        
        for(int potion : potions) potionCnt[potion] ++;

        int cnt = 0;
        //累积和
        for(int i = maxPotion; i >= 0; i --) {
            cnt += potionCnt[i];
            potionCnt[i] = cnt;
        }
        
        for(int i = 0; i < n; i++) {
           //这里target不要用int, 因为在spells[i]很小的时候，会溢出
            long target = success / spells[i];
            if(target > maxPotion) continue;

            while(target <= maxPotion && target * spells[i] < success) target ++;

            if(target > maxPotion) continue; //防止后面数组下标越界
            res[i] += potionCnt[(int)target];
        }
        return res;
        
    }
}