题解 | 咒语和药水的成功对数

题干分析:

题目给我们两个数组,一个基准值,要我们针对spells数组中的每一个值,寻找potions数组中与之相乘值大于基准值的个数.

算法思路:

很明显,针对每个spells数组中的值我们都得进行处理,因此我们这里考虑一个值的情况,设该值为s,基准值为k,即我们需要找到potions数组中大于k/s的值,针对potions[i],s,k,因此只要满足条件:

由于他们都是整数,所以:

同时为了更加方便的计数,我们不妨将positions进行排序,之后只要进行二分查找到符合要求的临界值然后计数即可.

实现代码:

vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        int n = static_cast<int>(spells.size());
        vector<int> ans(n);

        sort(potions.begin(), potions.end());

        for (int i = 0; i < n; ++i) {
            long long target = (success - 1) / spells[i]; // 注意除出来的数可能大于INT_MAX,因此要用long long
            if (target < potions.back())
                ans[i] = potions.end() - upper_bound(potions.begin(), potions.end(), static_cast<int>(target));
            else ans[i] = 0;
        }

        return ans;
    }

注: 这里其实可以不用另外开一个结果数组,由于spells数组的值只使用一次且大小与ans数组相等,可以直接用spells数组代替节省空间,只是个人不建议这么做,毕竟会直接覆盖spells数组中的原值(函数使用引用传参),而万一该数组原值之后还需要使用呢?

复杂度分析:

• 时间复杂度: 排序O(mlog m),二分O(log m),每个spells数组值一次二分操作因此为O(n log m).总计O((n + m)log m).
• 空间复杂度: 排序O(log m),结果存储O(n),总计O(n + log m).