Hard
题目描述
给你一个整数数组 nums，你可以在 nums 上执行下述操作 任意次：
- 如果
gcd(nums[i], nums[j]) > 1，交换nums[i]和nums[j]的位置。其中gcd(nums[i], nums[j])是nums[i]和nums[j]的最大公约数。
如果能使用上述交换方式将 nums 按 非递减顺序 排列，返回 true；否则，返回 false。
示例 1：
输入：nums = [7,21,3]
输出：true
解释：我们可以执行下述操作完成对 [7,21,3] 的排序：
- 交换 7 和 21 因为 gcd(7,21) = 7 > 1。nums = [21,7,3]
- 交换 21 和 3 因为 gcd(21,3) = 3 > 1。nums = [3,7,21]
示例 2：
输入：nums = [5,2,6,2]
输出：false
解释：无法完成排序，因为 5 不能与其他元素交换。
示例 3：
输入：nums = [10,5,9,3,15]
输出：true
解释：我们可以执行下述操作完成对 [10,5,9,3,15] 的排序：
- 交换 10 和 15 因为 gcd(10,15) = 5 > 1。nums = [15,5,9,3,10]
- 交换 15 和 3 因为 gcd(15,3) = 3 > 1。nums = [3,5,9,15,10]
- 交换 10 和 15 因为 gcd(10,15) = 5 > 1。nums = [3,5,9,10,15]
提示：
1 <= nums.length <= 3 * 10^42 <= nums[i] <= 10^5
解题思路
解题思路
这道题的核心思想是使用并查集来判断哪些位置的元素可以相互交换。
关键观察
- 如果两个数的最大公约数大于1，它们就可以交换位置
- 如果A能和B交换，B能和C交换，那么A、B、C三个数可以任意排列
- 这形成了一个连通性问题，可以用并查集解决
算法步骤
- 质因数分解：对每个数进行质因数分解，相同质因子的数可以相互交换
- 并查集构建：将具有相同质因子的数的索引进行合并
- 验证排序：检查排序后每个位置的数是否与原位置在同一个连通分量中
具体实现
- 使用筛法预处理每个数的最小质因子，便于快速分解
- 为每个质因子维护一个索引列表，将所有包含该质因子的数的索引合并到同一个连通分量
- 最后比较原数组和排序数组，验证每个位置的元素是否可以到达目标位置
时间复杂度主要在质因数分解和并查集操作上，整体较为高效。
代码实现
class Solution {
public:
vector<int> parent;
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void unite(int x, int y) {
parent[find(x)] = find(y);
}
bool gcdSort(vector<int>& nums) {
int n = nums.size();
parent.resize(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// 预处理最小质因子
vector<int> smallest_factor(100001);
for (int i = 0; i <= 100000; i++) {
smallest_factor[i] = i;
}
for (int i = 2; i * i <= 100000; i++) {
if (smallest_factor[i] == i) {
for (int j = i * i; j <= 100000; j += i) {
if (smallest_factor[j] == j) {
smallest_factor[j] = i;
}
}
}
}
// 为每个质因子维护索引列表
unordered_map<int, vector<int>> factor_to_indices;
for (int i = 0; i < n; i++) {
int num = nums[i];
unordered_set<int> factors;
// 质因数分解
while (num > 1) {
int factor = smallest_factor[num];
factors.insert(factor);
while (num % factor == 0) {
num /= factor;
}
}
// 将索引添加到对应的质因子列表中
for (int factor : factors) {
factor_to_indices[factor].push_back(i);
}
}
// 合并具有相同质因子的索引
for (auto& [factor, indices] : factor_to_indices) {
for (int i = 1; i < indices.size(); i++) {
unite(indices[0], indices[i]);
}
}
// 检查排序后的数组
vector<int> sorted_nums = nums;
sort(sorted_nums.begin(), sorted_nums.end());
for (int i = 0; i < n; i++) {
if (nums[i] != sorted_nums[i] && find(i) != find(lower_bound(nums.begin(), nums.end(), sorted_nums[i]) - nums.begin())) {
// 更精确的检查
bool found = false;
for (int j = 0; j < n; j++) {
if (nums[j] == sorted_nums[i] && find(i) == find(j)) {
found = true;
break;
}
}
if (!found) {
return false;
}
}
}
return true;
}
};
class Solution:
def gcdSort(self, nums: List[int]) -> bool:
n = len(nums)
parent = list(range(n))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def unite(x, y):
parent[find(x)] = find(y)
# 预处理最小质因子
smallest_factor = list(range(100001))
for i in range(2, int(100000**0.5) + 1):
if smallest_factor[i] == i:
for j in range(i*i, 100001, i):
if smallest_factor[j] == j:
smallest_factor[j] = i
# 为每个质因子维护索引列表
factor_to_indices = {}
for i, num in enumerate(nums):
factors = set()
# 质因数分解
temp = num
while temp > 1:
factor = smallest_factor[temp]
factors.add(factor)
while temp % factor == 0:
temp //= factor
# 将索引添加到对应的质因子列表中
for factor in factors:
if factor not in factor_to_indices:
factor_to_indices[factor] = []
factor_to_indices[factor].append(i)
# 合并具有相同质因子的索引
for indices in factor_to_indices.values():
for i in range(1, len(indices)):
unite(indices[0], indices[i])
# 检查排序后的数组
sorted_nums = sorted(nums)
for i in range(n):
if nums[i] != sorted_nums[i]:
# 检查是否存在相同值且在同一连通分量中
found = False
for j in range(n):
if nums[j] == sorted_nums[i] and find(i) == find(j):
found = True
break
if not found:
return False
return True
public class Solution {
private int[] parent;
private int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
private void Unite(int x, int y) {
parent[Find(x)] = Find(y);
}
public bool GcdSort(int[] nums) {
int n = nums.Length;
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// 预处理最小质因子
int[] smallestFactor = new int[100001];
for (int i = 0; i <= 100000; i++) {
smallestFactor[i] = i;
}
for (int i = 2; i * i <= 100000; i++) {
if (smallestFactor[i] == i) {
for (int j = i * i; j <= 100000; j += i) {
if (smallestFactor[j] == j) {
smallestFactor[j] = i;
}
}
}
}
// 为每个质因子维护索引列表
Dictionary<int, List<int>> factorToIndices = new Dictionary<int, List<int>>();
for (int i = 0; i < n; i++) {
int num = nums[i];
HashSet<int> factors = new HashSet<int>();
// 质因数分解
while (num > 1) {
int factor = smallestFactor[num];
factors.Add(factor);
while (num % factor == 0) {
num /= factor;
}
}
// 将索引添加到对应的质因子列表中
foreach (int factor in factors) {
if (!factorToIndices.ContainsKey(factor)) {
factorToIndices[factor] = new List<int>();
}
factorToIndices[factor].Add(i);
}
}
// 合并具有相同质因子的索引
foreach (var indices in factorToIndices.Values) {
for (int i = 1; i < indices.Count; i++) {
Unite(indices[0], indices[i]);
}
}
// 检查排序后的数组
int[] sortedNums = new int[n];
Array.Copy(nums, sortedNums, n);
Array.Sort(sortedNums);
for (int i = 0; i < n; i++) {
if (nums[i] != sortedNums[i]) {
// 检查是否存在相同值且在同一连通分量中
bool found = false;
for (int j = 0; j < n; j++) {
if (nums[j] == sortedNums[i] && Find(i) == Find(j)) {
found = true;
break;
}
}
if (!found) {
return false;
}
}
}
return true;
}
}
var gcdSort = function(nums) {
const n = nums.length;
const parent = Array.from({length: n}, (_, i) => i);
function find(x) {
if (parent[x] !== x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
function unite(x, y) {
parent[find(x)] = find(y);
}
// 预处理最小质因子
const smallestFactor = Array.from({length: 100001}, (_, i) => i);
for (let i = 2; i * i <= 100000; i++) {
if (smallestFactor[i]
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n√m + nlog n) | 其中 n 是数组长度，m 是数组中的最大 |
相关题目
- . Rank Transform of a Matrix (Hard)