https://leetcode-cn.com/contest/weekly-contest-257/problems/gcd-sort-of-an-array/
这题的主要思路就是,通过针对数组里面的元素做质数分解,找到联通分量,不同联通分量之间肯定是隔离的。然后针对每个联通分量进行排序,检查最后的结果是否完全排序。
在实现之前最好做一个估算:
- 因为元素范围是10^5, 所以质数量级大约在300左右(实际大约是100)
- 每个元素进行质数分解的话,这个数量级就是3 * 10^6
- 然后对每个元素做dfs, 这个数量级也是 3 * 10^4
- 因为每个联通分量是隔离的,所以排序的复杂度也是在 O(nlgn)
对于某个元素 nums[i] 进行质数p分解时,需要
- 在 groups[p] 里面添加i元素
- 同时在 backs[i] 里面添加p元素
这样如果i和j关联之后,那么可以通过backs[j]找到更多关联的质数。
寻找联通分量就是一个dfs的过程,但是这个过程不仅仅需要判断某个下标是否访问过,还需要判断某个质数是否访问过。因为如果某个质数群访问过的话,那么它下面所有的下标肯定也都访问过了。没有这个优化就会出现超时。
maski = [0] * len(nums)
maskp = set()
def dfs(i, idxs):
for p in backs[i]:
if p in maskp: continue
maskp.add(p)
for j in groups[p]:
if maski[j]:
continue
maski[j] = 1
idxs.append(j)
dfs(j, idxs)
下面是完整的代码,包括计算质数,判断是否有序,按照下标进行排序等。
def make_primes(K):
mask = [1] * (K + 1)
for i in range(2, K + 1):
if mask[i] == 0:
continue
for j in range(2, K + 1):
if i * j > K:
break
mask[i * j] = 0
primes = []
for i in range(2, K + 1):
if mask[i] == 1:
primes.append(i)
return primes
def issorted(nums):
for i in range(1, len(nums)):
if nums[i] < nums[i - 1]:
return False
return True
def sort_by_idxs(nums, idxs, tmps):
for j in idxs:
tmps.append(nums[j])
idxs.sort()
tmps.sort()
for j in range(len(idxs)):
nums[idxs[j]] = tmps[j]
class Solution:
def gcdSort(self, nums: List[int]) -> bool:
primes = make_primes(round(max(nums) ** 0.5) + 1)
if issorted(nums):
return True
from collections import defaultdict
groups = defaultdict(list)
backs = [[] for _ in range(len(nums))]
for i in range(len(nums)):
x = nums[i]
for p in primes:
if x < p: break
if x % p == 0:
while x % p == 0:
x = x // p
groups[p].append(i)
backs[i].append(p)
if x != 1:
groups[x].append(i)
backs[i].append(x)
maski = [0] * len(nums)
maskp = set()
def dfs(i, idxs):
for p in backs[i]:
if p in maskp: continue
maskp.add(p)
for j in groups[p]:
if maski[j]:
continue
maski[j] = 1
idxs.append(j)
dfs(j, idxs)
idxs = []
tmps = []
for i in range(len(nums)):
if maski[i] == 0:
idxs.clear()
tmps.clear()
maski[i] = 1
idxs.append(i)
dfs(i, idxs)
sort_by_idxs(nums, idxs, tmps)
return issorted(nums)