题解 | #排列询问#

排列询问

http://www.nowcoder.com/practice/99062f0877e047bb8c7374d241268a8b

题目理解:

从两个下标区间中各自读取一个数,判断这个两个数的最大公因数是否为其中较小的数,最后输出满足条件的数对的个数。

方法一

暴力搜索
第一重循环:遍历q个询问。
第二重循环:遍历询问i中,l1到r1之前的数字。
第三重循环:遍历询问i中,第二重循环里的每一个p[j]都与l2到r2之间的所有数字p[h]进行匹配判断。
判断是否有。不失一般性,设较小的数为a,较大的数为b,a也可以等于b。如果等式成立,说明a是两者的公因数,从而b可以被a整除;反过来,如果b可以被a整除,那么a是两者的公因数,并且公因数不会大于其中任意一个数字,所以a是两者的最大公因数。

遍历结果的示意图如下:
图片说明

具体代码如下:

class Solution {
public:
    vector<int> PermutationQuery(int n, int q, vector<int>& p, vector<int>& l1, vector<int>& r1, vector<int>& l2, vector<int>& r2) {
        vector<int> count;
        //三重循环
        for (int i=0;i<q;i++)
        {
            //把count中对应的部分初始化为0
            count.push_back(0);
            for (int j=l1[i];j<=r1[i];j++)
            {
                for (int h=l2[i];h<=r2[i];h++)
                {
                    //一个数是另外一个的倍数,则满足条件
                    if (max(p[j],p[h]) % min(p[j],p[h]) == 0) 
                        count[i]++;
                }
            }
        }
        return count;
    }
};

时间复杂度:。其中m是询问的个数,每一个询问需要一个两重循环来解决。
空间复杂度:。没有用到额外的任何空间。

方法二

贪心
不会

全部评论

相关推荐

点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 10:55
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务