题解 | #排列询问#
排列询问
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是询问的个数,每一个询问需要一个两重循环来解决。
空间复杂度:。没有用到额外的任何空间。
方法二
贪心
不会