文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题构建字典序最大的可行序列出处1718. 构建字典序最大的可行序列难度7 级题目描述要求给定一个整数n \texttt{n}n寻找满足下面条件的一个序列整数1 \texttt{1}1在序列中只出现一次。从2 \texttt{2}2到n \texttt{n}n的每个整数在序列中出现两次。对于每个2 \texttt{2}2到n \texttt{n}n之间的整数i \texttt{i}i两个i \texttt{i}i之间出现的距离恰好为i \texttt{i}i。序列中两个数a[i] \texttt{a[i]}a[i]和a[j] \texttt{a[j]}a[j]之间的距离是它们下标之差的绝对值|j − i| \texttt{|j} - \texttt{i|}|j−i|。返回满足上述条件的字典序最大的序列。题目保证在给定限制条件下一定存在解。一个序列a \texttt{a}a被认为比序列b \texttt{b}b两者长度相同字典序更大的条件是在a \texttt{a}a和b \texttt{b}b中第一个不一样的数字处a \texttt{a}a序列的数字比b \texttt{b}b序列的数字大。例如[0,1,9,0] \texttt{[0,1,9,0]}[0,1,9,0]比[0,1,5,6] \texttt{[0,1,5,6]}[0,1,5,6]字典序更大因为第一个不同的位置是第三个数字9 \texttt{9}9比5 \texttt{5}5大。示例示例 1输入n 3 \texttt{n 3}n 3输出[3,1,2,3,2] \texttt{[3,1,2,3,2]}[3,1,2,3,2]解释[2,3,2,1,3] \texttt{[2,3,2,1,3]}[2,3,2,1,3]也是一个可行的序列但是[3,1,2,3,2] \texttt{[3,1,2,3,2]}[3,1,2,3,2]是字典序最大的序列。示例 2输入n 5 \texttt{n 5}n 5输出[5,3,1,4,3,5,2,4,2] \texttt{[5,3,1,4,3,5,2,4,2]}[5,3,1,4,3,5,2,4,2]数据范围1 ≤ n ≤ 20 \texttt{1} \le \texttt{n} \le \texttt{20}1≤n≤20解法思路和算法整数1 11在序列中出现一次整数2 22到n nn在序列中各出现两次因此序列的长度是2 × n − 1 2 \times n - 12×n−1。可以使用回溯的做法生成符合要求的序列并找到符合要求的字典序最大的序列。一种错误的思路是按照从大到小的顺序依次枚举每个数字将大的数字尽可能填在序列中靠左的位置。该思路无法保证得到字典序最大的序列例如当n 5 n 5n5时该思路得到的序列是[ 5 , 2 , 4 , 2 , 3 , 5 , 4 , 3 , 1 ] [5, 2, 4, 2, 3, 5, 4, 3, 1][5,2,4,2,3,5,4,3,1]而字典序最大的序列是[ 5 , 3 , 1 , 4 , 3 , 5 , 2 , 4 , 2 ] [5, 3, 1, 4, 3, 5, 2, 4, 2][5,3,1,4,3,5,2,4,2]。为了得到符合要求的字典序最大的序列应该按照从左到右的顺序依次枚举每个下标在每个下标处填入尽可能大的数字。当从左到右的每个下标处都填入尽可能大的数字时可以得到字典序最大的序列。回溯过程中需要使用哈希集合存储已经使用过的数字。用index \textit{index}index表示遍历到的下标初始时index 0 \textit{index} 0index0。回溯的做法如下。如果index 2 × n − 1 \textit{index} 2 \times n - 1index2×n−1则所有数字都填入序列此时得到符合要求的序列该序列为符合要求的字典序最大的序列。如果序列的下标index \textit{index}index处已经填入数字则对下标index 1 \textit{index} 1index1继续回溯。如果序列的下标index \textit{index}index处尚未填入数字则对于从n nn到1 11的每个整数i ii执行如下操作。判断是否在序列中可以填入整数i ii。如果i 1 i 1i1则需要在下标index \textit{index}index处填入整数i ii如果i 1 i 1i1则需要在下标index i \textit{index} iindexi处填入整数i ii。如果整数i ii已经使用或者index i ≥ 2 × n − 1 \textit{index} i \ge 2 \times n - 1indexi≥2×n−1或者下标index i \textit{index} iindexi处已经填入数字则不能在序列中填入整数i ii。如果可以在序列中填入整数i ii则将整数i ii添加到哈希集合中在序列中填入整数i ii然后对下标index 1 \textit{index} 1index1继续回溯。如果尚未得到符合要求的序列则将整数i ii从哈希集合中移除在序列中撤销填入整数i ii的操作恢复到原始状态。由于题目保证一定存在解因此当回溯结束时即可得到符合要求的字典序最大的序列。实现方面由于填入序列的数字范围是[ 1 , n ] [1, n][1,n]因此可以使用数组代替哈希集合。代码classSolution{intn;int[]sequence;boolean[]used;booleanfoundfalse;publicint[]constructDistancedSequence(intn){this.nn;this.sequencenewint[2*n-1];this.usednewboolean[n1];backtrack(0);returnsequence;}publicvoidbacktrack(intindex){if(index2*n-1){foundtrue;}elseif(sequence[index]!0){backtrack(index1);}else{for(intin;i0;i--){intnexti1?index:indexi;if(used[i]||next2*n-1||sequence[next]!0){continue;}used[i]true;sequence[index]i;sequence[next]i;backtrack(index1);if(!found){used[i]false;sequence[index]0;sequence[next]0;}}}}}复杂度分析时间复杂度O ( ( 2 n ) n ) O((2n)^n)O((2n)n)其中n nn是给定的整数。回溯的一个宽松的时间复杂度上界是O ( ( 2 n ) n ) O((2n)^n)O((2n)n)实际回溯时由于在每个下标处都从大到小枚举待填入的数字因此实际时间复杂度远低于该上界。空间复杂度O ( n ) O(n)O(n)其中n nn是给定的整数。哈希集合和递归调用栈需要O ( n ) O(n)O(n)的空间。