题目描述

解析

  先对药水排序后每个咒语去二分查找最低满足的药水的位置。

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int n = spells.length, m = potions.length;
        Arrays.sort(potions);
        for (int i = 0; i < n; i++) {
            long target = (success - 1) / spells[i];
            if (target < potions[m - 1]) {
                spells[i] = m - binarySearch(potions, (int) target + 1);
            } else{
                spells[i] = 0;
            }
        }
        return spells;
    }

    private int binarySearch(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

  这题还有更快的解法，也就是示例代码最快的那个。代码首先找能满足的最低条件，相当于是一个剪枝操作，然后对于能满足的都在数组中加一，最后求前缀和，因为当前能够满足那么它之前的一定能满足，最后对应查找就行了。

class Solution {
   static int inf = (int)1e5;
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        
        int max = 0;
        for (int x:spells) 
           if(x > max) max = x;
       
        int minPotion = (int)Math.min(inf, (success+max-1) / max);
   
        int[] count = new int[max + 1];
        for (int potion : potions) {
            if (potion >= minPotion) 
                ++count[(int)((success + potion - 1) / potion)];
        }
        
        for (int i = 1; i <= max; i++)
            count[i] += count[i - 1];
            
        int n = spells.length;  
        int[] result = new int[n];         
        
        for (int i = 0; i < n; i++) 
            result[i] = count[spells[i]];
            
        return result;
    }
}