3886. 可排序整数求和网页链接力扣LeetCode力扣LeetCode 每日一题完成每日打卡即可获得力扣积分。获得相应数量的积分能在【力扣商店】换取相应奖品助力每日有题做丰盈积分日益多题目描述给你一个长度为n nn的整数数组nums。如果一个整数k kk满足以下条件则称其为可排序整数k kk是n nn的因数且可以通过依次执行以下操作将nums排序为非递减顺序将nums划分为长度为k kk的连续子数组。独立地对每个子数组进行循环移动左移或右移任意次数。返回所有可能的可排序整数k kk的和。子数组是数组中的一个连续、非空元素序列。输入描述一个长度为n nn的整数数组nums。输出描述返回所有可能的可排序整数k kk的和。示例 1输入nums [3,1,2]输出3解释对于n 3 n 3n3可能的因数是1 11和3 33。对于k 1 k 1k1每个子数组都只有一个元素。无法通过移动使数组排序。对于k 3 k 3k3单个子数组[ 3 , 1 , 2 ] [3, 1, 2][3,1,2]可以通过左移一次得到[ 1 , 2 , 3 ] [1, 2, 3][1,2,3]从而将数组排序。只有k 3 k 3k3可排序因此答案是3 33。示例 2输入nums [7,6,5]输出0解释对于n 3 n 3n3可能的因数是1 11和3 33。对于k 1 k 1k1每个子数组都只有一个元素。无法通过移动使数组排序。对于k 3 k 3k3单个子数组[ 7 , 6 , 5 ] [7, 6, 5][7,6,5]无法通过任何移动排序为非递减顺序。没有任何可排序的k kk因此答案是0 00。示例 3输入nums [5,8]输出3解释对于n 2 n 2n2可能的因数是1 11和2 22。由于[ 5 , 8 ] [5, 8][5,8]本身已经有序每个因数都可排序。因此答案是1 2 3 1 2 3123。数据范围1 ≤ n nums.length ≤ 10 5 1 \le n \text{nums.length} \le 10^51≤nnums.length≤1051 ≤ nums [ i ] ≤ 10 5 1 \le \text{nums}[i] \le 10^51≤nums[i]≤105解题思路本题是因数枚举 下降点预处理 分块循环有序性判定问题。给定长度为n nn的数组nums可排序整数k kk必须满足k ∣ n k \mid nk∣n并且把数组按下标从0 00开始划分为若干个长度为k kk的连续子数组后每个子数组可以独立进行循环移动使得整个数组最终非递减。由于划分方式由k kk唯一确定因此只需枚举n nn的所有因数并判断每个因数是否可行。1. 问题等价转化对于固定的k kk数组被划分为n / k n/kn/k个块[ s , t ] [ j k , ( j 1 ) k − 1 ] [s,t][jk,(j1)k-1][s,t][jk,(j1)k−1]每个块内部可以任意循环移动但不改变块内元素集合。要使整个数组非递减需要满足每个块经过循环移动后块内序列非递减后一个块的首元素不小于前一个块的末元素。因此判断一个k kk是否可行等价于从左到右检查每个块能否通过循环移动变成非递减并维护上一块的末元素。2. 预处理下降点数组d定义d[i]表示从下标i开始向右遇到的第一个下降位置即第一个满足n u m s [ p ] n u m s [ p 1 ] nums[p] nums[p1]nums[p]nums[p1]的位置p pp如果不存在则记为n nn。代码从右向左预处理初始d[n-1] n若nums[u] nums[u1]则令j u否则继承右侧的下降点最后d[u] j。于是区间[l,r]非递减的充要条件为d [ l ] ≥ r d[l] \ge rd[l]≥r这样就能在O ( 1 ) O(1)O(1)时间内判断任意块是否本身非递减。3. 判定单个因数k对于块[s,t]其中t s k - 1令q d [ s ] q d[s]qd[s]分两种情况情况一q t说明块[s,t]本身已经非递减不需要循环移动。此时块首为nums[s]块末为nums[t]。需要检查nums[s] x其中x表示上一块的末元素检查通过后更新x nums[t]。情况二q t说明块内存在下降点且q是第一个下降点。若该块能通过循环移动变成非递减唯一可能的方式是把[q1,t]移到前面把[s,q]移到后面即变成[ q 1 , t ] [ s , q ] [q1,t] [s,q][q1,t][s,q]需要同时满足后半段[q1,t]非递减即d[q1] t两段连接处满足nums[t] nums[s]新块首nums[q1]不小于上一块末元素x即nums[q1] x前半段[s,q]非递减这一点由q d[s]自然保证。若全部满足则更新x nums[q]因为循环移动后块末元素为nums[q]。若任意一个块检查失败则当前k不可排序否则把k加入答案。4. 枚举所有因数只需枚举1 ≤ e ≤ n 1 \le e \le \sqrt n1≤e≤n​若n % e 0则e和n/e都是因数检查e若e * e ! n再检查n/e避免重复。5. 复杂度分析预处理下降点数组O ( n ) O(n)O(n)枚举因数O ( n ) O(\sqrt n)O(n​)对因数k kk需要检查n / k n/kn/k个块每块O ( 1 ) O(1)O(1)。总检查次数为∑ k ∣ n n k ∑ d ∣ n d σ ( n ) \sum_{k \mid n} \frac{n}{k} \sum_{d \mid n} d \sigma(n)k∣n∑​kn​d∣n∑​dσ(n)因此时间复杂度为O ( n σ ( n ) ) O(n \sigma(n))O(nσ(n))其中σ ( n ) \sigma(n)σ(n)为n nn的约数之和空间复杂度为O ( n ) O(n)O(n)。总结先预处理每个位置向右的第一个下降点从而O ( 1 ) O(1)O(1)判断任意区间是否非递减。枚举n nn的所有因数k kk对每个块判断它本身是否非递减或是否存在唯一的切分点使其循环移动后非递减并检查块间衔接关系。所有可行k kk累加即为答案。代码内容classSolution{public:intsortableIntegers(vectorintnums){intNnums.size();vectorintd(N);d[N-1]N;intjN;for(intuN-2;u0;u--){if(nums[u]nums[u1])ju;d[u]j;}inta0;autof[](intw)-void{intx0;for(inttw-1;tN;tw){intst-w1;intqd[s];if(qt){if(nums[s]x)return;xnums[t];}else{if(d[q1]t||nums[q1]x||nums[t]nums[s])return;xnums[q];}}aw;};for(inte1;e*eN;e){if(N%e0){f(e);if(e*eN)f(N/e);}}returna;}};