用小程序做视频网站,有哪些网站可以做店面设计软件,微网站建设 上海,廊坊建设企业网站Leetcode 3312. Sorted GCD Pair Queries 1. 解题思路2. 代码实现 题目链接#xff1a;3312. Sorted GCD Pair Queries
1. 解题思路
这一题的话坦率来说没有搞定#xff0c;后来是找的大佬的代码抄了一下……
整体来说这道题思路上还是比较暴力的#xff0c;还是一个二重…Leetcode 3312. Sorted GCD Pair Queries 1. 解题思路2. 代码实现 题目链接3312. Sorted GCD Pair Queries
1. 解题思路
这一题的话坦率来说没有搞定后来是找的大佬的代码抄了一下……
整体来说这道题思路上还是比较暴力的还是一个二重循环不过我是最暴力的二重循环大佬稍微做了一下优化……
首先给出我的代码如下
class Solution:def gcdValues(self, nums: List[int], queries: List[int]) - List[int]:cnt Counter(nums)nums sorted(cnt.keys())m max(nums)s [0 for _ in range(m1)]n len(nums)for i in range(n):x nums[i]s[x] cnt[x] * (cnt[x]-1) // 2for j in range(i1, n):y nums[j]c gcd(x, y)s[c] cnt[x] * cnt[y]s list(accumulate(s))return [bisect.bisect_right(s, q) for q in queries]可以看到就是两两求最大公约数然后通过二分检索的方式求query的结果。而这个方法不出所料地超时了。
然后大佬们的优化点在于不是两两求最大公约数了而是直接将所有可能的因数罗列出来然后求每一个数作为最大公约数时的个数。
而对于具体的求法类似于求全部质数即对每一个数其作为最大公约数的个数为所有倍数上的数的个数总和取 C n 2 C_n^2 Cn2然后减去其倍数上所有的数的最大公约数的数目。
如此一来的话差不多就是将时间复杂度从 O ( N 2 ) O(N^2) O(N2)减至 O ( N 3 / 2 ) O(N^{3/2}) O(N3/2)。
2. 代码实现
给出python代码实现如下
class Solution:def gcdValues(self, nums: List[int], queries: List[int]) - List[int]:cnt Counter(nums)nums sorted(cnt.keys())m max(nums)s [0 for _ in range(m1)]for i in range(m,0,-1):vc sum(cnt[x] for x in range(i,m1,i))vc vc*(vc-1)//2 - sum(s[x] for x in range(i,m1,i))s[i]vcs list(accumulate(s))return [bisect.bisect_right(s, q) for q in queries]提交代码评测得到耗时1627ms占用内存42.2MB。
