来源第 495 场周赛 Q3难度困难分数1999
题目描述
给你一个长度为 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 <= 105 1 <= nums[i] <= 105
解法
方法一:枚举 + 模拟
思考
若对每个因数的每一段都尝试全部 \(k\) 种循环移位,单段比较就是 \(O(k^2)\)。 \(n \le 10^5\) 时,这一做法会超出时间限制。
开销集中在同一段被反复旋转。一段经循环移位后能变成非递减,当且仅当首尾相接后严格下降至多出现一次。各段都旋成非递减之后,每个分界处还要满足左侧最大值不超过右侧最小值,拼接结果才会全局非递减。
下降次数和两侧最值都落在段的边界上。
我们预处理前缀最大值、后缀最小值和相邻下降的前缀和,再枚举 \(n\) 的因数,对每一段用 \(O(1)\) 时间完成判断。
先求出三个辅助数组。 \(\textit{prefMax}[i]\) 是 \(\textit{nums}[0..i-1]\) 的最大值, \(\textit{prefMax}[0] = 0\)。 \(\textit{suffMin}[i]\) 是 \(\textit{nums}[i..n-1]\) 的最小值。 \(\textit{prefDrop}[i]\) 统计下标对 \((0,1),\ldots,(i-1,i)\) 中 \(\textit{nums}[j-1] > \textit{nums}[j]\) 的次数。
接着枚举 \(n\) 的每个因数 \(k\),把数组分成若干长度为 \(k\) 的段。对起点 \(i\),段内相邻下降次数为 \(\textit{prefDrop}[i+k-1] - \textit{prefDrop}[i]\),若 \(\textit{nums}[i+k-1] > \textit{nums}[i]\) 再加一次。这个总数不超过 \(1\),并且 \(\textit{prefMax}[i] \le \textit{suffMin}[i]\) 时,该段可以通过循环移位接到前面的有序部分之后。全部分段都通过,就把 \(k\) 加入答案。
时间复杂度 \(O(n + \sigma(n))\),空间复杂度 \(O(n)\)。其中 \(n\) 是数组长度, \(\sigma(n)\) 是 \(n\) 的全部正因数之和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 | class Solution:
def sortableIntegers(self, nums: list[int]) -> int:
n = len(nums)
pref_max = [0] * (n + 1)
for i, x in enumerate(nums):
pref_max[i + 1] = max(pref_max[i], x)
suff_min = [10**9] * (n + 1)
for i in range(n - 1, -1, -1):
suff_min[i] = min(nums[i], suff_min[i + 1])
pref_drop = [0] * n
for i in range(1, n):
pref_drop[i] = pref_drop[i - 1] + (nums[i - 1] > nums[i])
def check(k: int) -> bool:
for start in range(0, n, k):
end = start + k - 1
drops = pref_drop[end] - pref_drop[start]
if nums[end] > nums[start]:
drops += 1
if drops > 1 or pref_max[start] > suff_min[start]:
return False
return True
ans = 0
i = 1
while i <= n // i:
if n % i == 0:
if check(i):
ans += i
other = n // i
if i != other and check(other):
ans += other
i += 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45 | class Solution {
public int sortableIntegers(int[] nums) {
int n = nums.length;
int[] prefMax = new int[n + 1];
for (int i = 0; i < n; ++i) {
prefMax[i + 1] = Math.max(prefMax[i], nums[i]);
}
int[] suffMin = new int[n + 1];
suffMin[n] = 1000000000;
for (int i = n - 1; i >= 0; --i) {
suffMin[i] = Math.min(nums[i], suffMin[i + 1]);
}
int[] prefDrop = new int[n];
for (int i = 1; i < n; ++i) {
prefDrop[i] = prefDrop[i - 1] + (nums[i - 1] > nums[i] ? 1 : 0);
}
int ans = 0;
for (int i = 1; i <= n / i; ++i) {
if (n % i == 0) {
if (check(nums, prefMax, suffMin, prefDrop, i)) {
ans += i;
}
if (i != n / i && check(nums, prefMax, suffMin, prefDrop, n / i)) {
ans += n / i;
}
}
}
return ans;
}
private boolean check(int[] nums, int[] prefMax, int[] suffMin, int[] prefDrop, int k) {
int n = nums.length;
for (int start = 0; start < n; start += k) {
int end = start + k - 1;
int drops = prefDrop[end] - prefDrop[start];
if (nums[end] > nums[start]) {
++drops;
}
if (drops > 1 || prefMax[start] > suffMin[start]) {
return false;
}
}
return true;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43 | class Solution {
public:
int sortableIntegers(vector<int>& nums) {
int n = nums.size();
vector<int> prefMax(n + 1);
for (int i = 0; i < n; ++i) {
prefMax[i + 1] = max(prefMax[i], nums[i]);
}
vector<int> suffMin(n + 1, 1000000000);
for (int i = n - 1; i >= 0; --i) {
suffMin[i] = min(nums[i], suffMin[i + 1]);
}
vector<int> prefDrop(n);
for (int i = 1; i < n; ++i) {
prefDrop[i] = prefDrop[i - 1] + (nums[i - 1] > nums[i]);
}
auto check = [&](int k) {
for (int start = 0; start < n; start += k) {
int end = start + k - 1;
int drops = prefDrop[end] - prefDrop[start];
if (nums[end] > nums[start]) {
++drops;
}
if (drops > 1 || prefMax[start] > suffMin[start]) {
return false;
}
}
return true;
};
int ans = 0;
for (int i = 1; i <= n / i; ++i) {
if (n % i == 0) {
if (check(i)) {
ans += i;
}
if (i != n / i && check(n / i)) {
ans += n / i;
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 | func sortableIntegers(nums []int) int {
n := len(nums)
prefMax := make([]int, n+1)
for i, x := range nums {
prefMax[i+1] = max(prefMax[i], x)
}
suffMin := make([]int, n+1)
suffMin[n] = 1000000000
for i := n - 1; i >= 0; i-- {
suffMin[i] = min(nums[i], suffMin[i+1])
}
prefDrop := make([]int, n)
for i := 1; i < n; i++ {
prefDrop[i] = prefDrop[i-1]
if nums[i-1] > nums[i] {
prefDrop[i]++
}
}
check := func(k int) bool {
for start := 0; start < n; start += k {
end := start + k - 1
drops := prefDrop[end] - prefDrop[start]
if nums[end] > nums[start] {
drops++
}
if drops > 1 || prefMax[start] > suffMin[start] {
return false
}
}
return true
}
ans := 0
for i := 1; i <= n/i; i++ {
if n%i == 0 {
if check(i) {
ans += i
}
if i != n/i && check(n/i) {
ans += n / i
}
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43 | function sortableIntegers(nums: number[]): number {
const n = nums.length;
const prefMax = new Array<number>(n + 1).fill(0);
for (let i = 0; i < n; i++) {
prefMax[i + 1] = Math.max(prefMax[i], nums[i]);
}
const suffMin = new Array<number>(n + 1).fill(1e9);
for (let i = n - 1; i >= 0; i--) {
suffMin[i] = Math.min(nums[i], suffMin[i + 1]);
}
const prefDrop = new Array<number>(n).fill(0);
for (let i = 1; i < n; i++) {
prefDrop[i] = prefDrop[i - 1] + (nums[i - 1] > nums[i] ? 1 : 0);
}
const check = (k: number): boolean => {
for (let start = 0; start < n; start += k) {
const end = start + k - 1;
let drops = prefDrop[end] - prefDrop[start];
if (nums[end] > nums[start]) {
drops++;
}
if (drops > 1 || prefMax[start] > suffMin[start]) {
return false;
}
}
return true;
};
let ans = 0;
for (let i = 1; i <= Math.floor(n / i); i++) {
if (n % i === 0) {
const other = n / i;
if (check(i)) {
ans += i;
}
if (i !== other && check(other)) {
ans += other;
}
}
}
return ans;
}
|