最大公约数遍历

难度: Hard

给你一个下标从 0 开始的整数数组 nums ，你可以在一些下标之间遍历。对于两个下标 i 和 j（i != j），当且仅当 gcd(nums[i], nums[j]) > 1 时，我们可以在两个下标之间通行，其中 gcd 是两个数的 最大公约数 。

你需要判断 nums 数组中任意两个满足 i < j 的下标 i 和 j ，是否存在若干次通行可以从 i 遍历到 j 。

如果任意满足条件的下标对都可以遍历，那么返回 true ，否则返回 false 。

示例 1：

输入：nums = [2,3,6]
输出：true
解释：这个例子中，总共有 3 个下标对：(0, 1) ，(0, 2) 和 (1, 2) 。
从下标 0 到下标 1 ，我们可以遍历 0 -> 2 -> 1 ，我们可以从下标 0 到 2 是因为 gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1 ，从下标 2 到 1 是因为 gcd(nums[2], nums[1]) = gcd(6, 3) = 3 > 1 。
从下标 0 到下标 2 ，我们可以直接遍历，因为 gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1 。同理，我们也可以从下标 1 到 2 因为 gcd(nums[1], nums[2]) = gcd(3, 6) = 3 > 1 。

示例 2：

输入：nums = [3,9,5]
输出：false
解释：我们没法从下标 0 到 2 ，所以返回 false 。

示例 3：

输入：nums = [4,3,12,8]
输出：true
解释：总共有 6 个下标对：(0, 1) ，(0, 2) ，(0, 3) ，(1, 2) ，(1, 3) 和 (2, 3) 。所有下标对之间都存在可行的遍历，所以返回 true 。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

Submission

运行时间: 70 ms

内存: 29.7 MB

class Solution:
    def canTraverseAllPairs(self, nums: List[int]) -> bool:
        length = len(nums)
        if length == 1 : return True
        if 1 in nums: return False
        nums = sorted(set(nums), reverse = True)

        if ( length:=len(nums)) == 1: return True
        
        for i in range(length - 1):
            for j in range(i+1, length):
                if gcd(nums[i],nums[j]) - 1:
                    nums[j] *= nums[i]
                    break
            else:
                return False        
        
        return True

Explain

The given solution tries to determine if any pair of indices in the array can be traversed using the greatest common divisor (gcd) condition. It first checks trivial cases such as single-element arrays and arrays containing the number '1'. Afterwards, it removes duplicates and sorts the array in descending order. The code then attempts to check if, for each element, there exists another element with a gcd greater than 1. If it finds such a pair, it modifies the second element by multiplying it with the first, presumably to increase future gcd values artificially. If it cannot find any such pair for any element, it returns False, otherwise True if all elements can be paired up successfully.

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def canTraverseAllPairs(self, nums: List[int]) -> bool:
        length = len(nums)
        if length == 1 : return True  # If there's only one element, traversal is trivially possible
        if 1 in nums: return False  # '1' cannot have gcd greater than 1 with any number
        nums = sorted(set(nums), reverse = True)  # Remove duplicates and sort in descending order

        if ( length:=len(nums)) == 1: return True  # Check again in case of single unique element

        for i in range(length - 1):
            for j in range(i+1, length):
                if gcd(nums[i],nums[j]) > 1:  # Check if gcd is greater than 1
                    nums[j] *= nums[i]  # Modify the number to potentially increase future gcd calculations
                    break
            else:  # No valid gcd found for current element 'i'
                return False  # Not all pairs can be traversed
        return True  # All pairs can be traversed if the loop completes

Explore

去除重复元素是为了简化问题，避免重复计算和处理相同元素对最大公约数的影响，从而提高算法效率。排序则是为了让数组中的元素按照一定顺序排列，这样在遍历寻找满足条件的元素对时，可以更快地确定是否存在有效的最大公约数对。特别是在降序排序后，可以优先处理较大的数，这有助于快速找到满足条件的数对，因为较大的数更有可能与其它数有较大的最大公约数。

在这种算法中，一旦数组中存在数字1，算法需要判定能否通过最大公约数连接任意一对数字。但由于1与任何数的最大公约数都是1，这意味着1不能与任何其他数形成最大公约数大于1的对。因此，如果数组中含有1，就无法满足题目要求的遍历所有数对的条件，直接返回False是一个有效的提前终止判断，节省了不必要的计算。

在算法中修改第二个元素（nums[j]）乘以第一个元素（nums[i]）的目的在于尝试人为地增加数组中元素的值，以此增加后续可能的最大公约数计算值。这种改变基于假设通过增加数值大小可能会产生更多的公约数，进而有更多机会找到满足条件的数对。然而，这种做法并不总是有效，并且可能导致算法的复杂性增加，因为修改元素值也可能破坏原有的最大公约数关系，使问题更加复杂。

在这个算法中，只修改`nums[j]`而不修改`nums[i]`主要是因为在遍历过程中，`nums[i]`作为起始参照点，如果修改了`nums[i]`，将影响后续所有的比较和计算，增加处理的复杂度。而修改`nums[j]`则是在找到满足条件的一对后，尝试改变其值以便后续操作可能利用新的值生成更大的最大公约数。这种修改虽然可以在某些情况下帮助找到解决方案，但实际上可能会降低算法的准确性和预测性，因为它改变了数组的自然组成，可能导致算法无法正确判断所有情况。