Hard
题目描述
给你一个长度为 n 的整数数组 nums。
如果一个整数 k 满足以下条件，则称为可排序的：
- k 能整除 n
- 你可以通过依次执行以下操作将 nums 按非递减顺序排序：
- 将 nums 分割成长度为 k 的连续子数组
- 独立地将每个子数组向左或向右循环旋转任意次数
返回所有可能的可排序整数 k 的和。
示例 1：
输入：nums = [3,1,2]
输出：3
解释：
- 对于 n = 3，可能的除数是 1 和 3。
- 对于 k = 1：每个子数组只有一个元素。旋转无法排序数组。
- 对于 k = 3：单个子数组 [3, 1, 2] 可以旋转一次得到 [1, 2, 3]，这是有序的。
- 只有 k = 3 是可排序的。因此，答案是 3。
示例 2：
输入：nums = [7,6,5]
输出：0
解释：
- 对于 n = 3，可能的除数是 1 和 3。
- 对于 k = 1：每个子数组只有一个元素。旋转无法排序数组。
- 对于 k = 3：单个子数组 [7, 6, 5] 无法通过旋转变成非递减顺序。
- 没有 k 是可排序的。因此，答案是 0。
示例 3：
输入：nums = [5,8]
输出：3
解释：
- 对于 n = 2，可能的除数是 1 和 2。
- 由于 [5, 8] 已经有序，每个除数都是可排序的。因此，答案是 1 + 2 = 3。
约束条件：
- 1 <= n == nums.length <= 10^5
- 1 <= nums[i] <= 10^5
解题思路
这道题的核心思路是理解什么时候一个子数组可以通过循环旋转变成有序状态。
关键观察：
- k 必须是 n 的因数，因为我们需要将数组分割成长度为 k 的连续子数组
- 对于每个长度为 k 的子数组，我们需要检查它是否可以通过循环旋转变成对应位置在排序后数组中的子数组
算法步骤：
- 首先获取原数组的排序版本
sorted_nums - 找到 n 的所有因数
- 对于每个因数 k，检查是否可排序：
- 将数组分成长度为 k 的块
- 对于每个块，检查原始块是否可以通过循环旋转得到对应的排序块
- 判断循环旋转的技巧：将原始块复制两遍连接，然后检查排序块是否出现在这个双倍长度的字符串中
循环旋转检查的原理： 如果一个数组 A 可以通过循环旋转得到数组 B，那么 B 必然是 A+A（A 连接自身）的一个子串。例如：[3,1,2] 旋转后可以得到 [1,2,3]，而 [1,2,3] 确实出现在 [3,1,2,3,1,2] 中。
代码实现
class Solution {
public:
int sortableIntegers(vector<int>& nums) {
int n = nums.size();
vector<int> sorted_nums = nums;
sort(sorted_nums.begin(), sorted_nums.end());
int result = 0;
// 遍历所有 n 的因数
for (int k = 1; k <= n; k++) {
if (n % k != 0) continue;
bool is_sortable = true;
// 检查每个长度为 k 的块
for (int i = 0; i < n; i += k) {
vector<int> original_block(nums.begin() + i, nums.begin() + i + k);
vector<int> sorted_block(sorted_nums.begin() + i, sorted_nums.begin() + i + k);
// 检查是否可以通过循环旋转得到
if (!canRotateTo(original_block, sorted_block)) {
is_sortable = false;
break;
}
}
if (is_sortable) {
result += k;
}
}
return result;
}
private:
bool canRotateTo(vector<int>& original, vector<int>& target) {
if (original.size() != target.size()) return false;
// 将原始数组复制两遍
vector<int> doubled = original;
doubled.insert(doubled.end(), original.begin(), original.end());
// 检查目标数组是否出现在doubled中
for (int i = 0; i <= (int)original.size(); i++) {
bool match = true;
for (int j = 0; j < (int)target.size(); j++) {
if (doubled[i + j] != target[j]) {
match = false;
break;
}
}
if (match) return true;
}
return false;
}
};
class Solution:
def sortableIntegers(self, nums: list[int]) -> int:
n = len(nums)
sorted_nums = sorted(nums)
result = 0
# 遍历所有 n 的因数
for k in range(1, n + 1):
if n % k != 0:
continue
is_sortable = True
# 检查每个长度为 k 的块
for i in range(0, n, k):
original_block = nums[i:i+k]
sorted_block = sorted_nums[i:i+k]
# 检查是否可以通过循环旋转得到
if not self.can_rotate_to(original_block, sorted_block):
is_sortable = False
break
if is_sortable:
result += k
return result
def can_rotate_to(self, original, target):
if len(original) != len(target):
return False
# 将原始数组复制两遍
doubled = original + original
# 检查目标数组是否出现在doubled中
for i in range(len(original) + 1):
if doubled[i:i+len(target)] == target:
return True
return False
public class Solution {
public int SortableIntegers(int[] nums) {
int n = nums.Length;
int[] sortedNums = new int[n];
Array.Copy(nums, sortedNums, n);
Array.Sort(sortedNums);
int result = 0;
// 遍历所有 n 的因数
for (int k = 1; k <= n; k++) {
if (n % k != 0) continue;
bool isSortable = true;
// 检查每个长度为 k 的块
for (int i = 0; i < n; i += k) {
int[] originalBlock = new int[k];
int[] sortedBlock = new int[k];
Array.Copy(nums, i, originalBlock, 0, k);
Array.Copy(sortedNums, i, sortedBlock, 0, k);
// 检查是否可以通过循环旋转得到
if (!CanRotateTo(originalBlock, sortedBlock)) {
isSortable = false;
break;
}
}
if (isSortable) {
result += k;
}
}
return result;
}
private bool CanRotateTo(int[] original, int[] target) {
if (original.Length != target.Length) return false;
// 将原始数组复制两遍
int[] doubled = new int[original.Length * 2];
Array.Copy(original, 0, doubled, 0, original.Length);
Array.Copy(original, 0, doubled, original.Length, original.Length);
// 检查目标数组是否出现在doubled中
for (int i = 0; i <= original.Length; i++) {
bool match = true;
for (int j = 0; j < target.Length; j++) {
if (doubled[i + j] != target[j]) {
match = false;
break;
}
}
if (match) return true;
}
return false;
}
}
var sortableIntegers = function(nums) {
const n = nums.length;
const sortedNums = [...nums].sort((a, b) => a - b);
let result = 0;
// 遍历所有 n 的因数
for (let k = 1; k <= n; k++) {
if (n % k !== 0) continue;
let isSortable = true;
// 检查每个长度为 k 的块
for (let i = 0; i < n; i += k) {
const originalBlock = nums.slice(i, i + k);
const sortedBlock = sortedNums.slice(i, i + k);
// 检查是否可以通过循环旋转得到
if (!canRotateTo(originalBlock, sortedBlock)) {
isSortable = false;
break;
}
}
if (isSortable) {
result += k;
}
}
return result;
};
function canRotateTo(original, target) {
if (original.length !== target.length) return false;
// 将原始数组复制两遍
const doubled = original.concat(original);
// 检查目标数组是否出现在doubled中
for (let i = 0; i <= original.length; i++) {
let match = true;
for (let j = 0; j < target.length; j++) {
if (doubled[i + j] !== target[j]) {
match = false;
break;
}
}
if (match) return true;
}
return false;
}
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n² × d(n)) | 其中 d(n) 是 n 的因数个数，对于每个因数需要检查 O(n) 个块，每个块的旋转检查需要 O(k) 时间 |
| 空间复杂度 | O(n) | 需要存储排序后的数组和临时块数组 |