题目大意 给定一个长度为 nnn 的数组，对进行如下操作： 1. 从数组中任意选择 222 个不同数字 2. 同时交换两个数字的最高位和最低位 3. 交换后的两个数字都不在原数组中，那么用空格将交换后的数字串联起来，从而生成一个有效的数字组合 4. 否则，不是一个有效的数字组合 求可以生成多少个不同且有效的新数字组合。 题意分析 样例 111 中 123344 和 8004，虽然这样的两个数字完全不一样，但如果进行了交换，会得到数字 823344，它在原数组中，不符合题目要求。 又例如数组 = [102，112，122，927，937，947]，将其分为两组： * 第一组：102，112，122 * 第二组：927，937，947 其中第一组内的数字不能进行最高位和最低位的交换，因为交换后数字不变，必然在原数组中，第二组也同理。 考虑交换第一组和第二组的数字。 * 第一组的 122 无法与第二组的任何数字交换，因为交换后会得到 927，它在原数组中 * 第二组的 927 无法与第一组的任何数字交换，因为交换后会得到 122，它在原数组中 * 其余数字对可以交换最高位和最低位 解题思路 按照最高位和最低位，将数组分成至多 90 组数字，从 10 到 99。 例如数组 = [102，112，122，927，937，947]，分成如下两组（去掉最高位和最低位）： * AAA 组：0，1，2 * BBB 组：2，3，4 分组后，只需要去掉组中相同的数字，然后求出排列数情况就是 AAA 组和 BBB 组可以生成的新数字数量。 上述案例中 AAA 和 BBB 相同的数字有 111 个，不同且有效的新数字组合数为 (3−1)∗(3−1)∗2=8(3-1)*(3-1)*2=8(3−1)∗(3−1)∗2=8 枚举所有组对，同上述计算方法，累加起来即为答案。 时间复杂度解析 此程序时间复杂度为 O(NM∣∑∣)O(NM \vert \sum \vert)O(NM∣∑∣)，NNN 为数组长度， MMM 为数字长度，∣∑∣=90\vert \sum \vert = 90∣∑∣=90 是首尾数字组合集合的大小。 枚举组对的逻辑看上去是 O(NM∣∑∣2)O(NM \vert \sum \vert^2)O(NM∣∑∣2) 的，但去掉内层 O(∣∑∣)O(\vert \sum \vert)O(∣∑∣) 的循环后，剩余循环相当于把数组遍历一遍，是 O(NM)O(NM)O(NM)，所以总的时间复杂度是 O(NM∣∑∣)O(NM \vert \sum \vert)O(NM∣∑∣)。 代码演示