跳转至

3886. 可排序整数求和

来源第 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;
}

评论