Hard
题目描述
注意：在这个版本中，可以执行的操作次数增加到了两次。
给你一个由正整数组成的数组 nums。
如果两个整数 x 和 y 在执行以下操作最多两次后可以变得相等，我们称它们为几乎相等：
- 选择 x 或 y 中的一个，交换所选数字内的任意两位数字。
返回数组 nums 中满足 i < j 且 nums[i] 和 nums[j] 几乎相等的下标对 (i, j) 的数目。
注意，执行操作后，整数可以有前导零。
示例 1：
输入：nums = [1023,2310,2130,213]
输出：4
解释：
几乎相等的元素对有：
- 1023 和 2310。通过交换 1023 中的数字 1 和 2，然后交换数字 0 和 3，得到 2310。
- 1023 和 213。通过交换 1023 中的数字 1 和 0，然后交换数字 1 和 2，得到 0213，即 213。
- 2310 和 213。通过交换 2310 中的数字 2 和 0，然后交换数字 3 和 2，得到 0213，即 213。
- 2310 和 2130。通过交换 2310 中的数字 3 和 1，得到 2130。
示例 2：
输入：nums = [1,10,100]
输出：3
解释：
几乎相等的元素对有：
- 1 和 10。通过交换 10 中的数字 1 和 0，得到 01，即 1。
- 1 和 100。通过交换 100 中第二个 0 和数字 1，得到 001，即 1。
- 10 和 100。通过交换 100 中第一个 0 和数字 1，得到 010，即 10。
提示：
2 <= nums.length <= 50001 <= nums[i] < 10^7
提示：
- 对于每个元素，找出通过应用操作可以得到的所有可能整数。
- 将所有整数的频率存储在哈希映射中。
解题思路
解题思路
这道题要求找出所有"几乎相等"的数对，其中两个数在最多进行两次交换操作后可以变得相等。
核心思路
生成所有可能的变换结果：对于每个数字，我们需要找出通过最多两次交换操作能得到的所有可能的数字。
分类讨论交换次数：
- 0次交换：数字本身
- 1次交换：选择任意两个位置进行交换
- 2次交换：在1次交换的基础上，再进行一次交换
使用哈希表统计：将每个数字能变换成的所有可能结果存入哈希表，然后统计相同结果的出现次数。
具体实现
首先，我们需要一个函数来生成某个数字的所有可能变换结果。对于每个数字：
- 转换为字符串便于操作
- 枚举所有可能的交换组合（0次、1次、2次）
- 将结果转回整数并去重
然后遍历数组，对每个数字生成其变换集合，在哈希表中查找已有的匹配数字，累加答案。
这种方法的优势是避免了两两比较的O(n²)复杂度中每次都要重新计算变换，而是预处理好所有可能的变换结果。
代码实现
class Solution {
public:
vector<int> getTransforms(int num) {
string s = to_string(num);
set<int> results;
// 0次交换
results.insert(num);
// 1次交换
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j < s.length(); j++) {
string temp = s;
swap(temp[i], temp[j]);
results.insert(stoi(temp));
}
}
// 2次交换
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j < s.length(); j++) {
string temp = s;
swap(temp[i], temp[j]);
for (int k = 0; k < temp.length(); k++) {
for (int l = k + 1; l < temp.length(); l++) {
string temp2 = temp;
swap(temp2[k], temp2[l]);
results.insert(stoi(temp2));
}
}
}
}
return vector<int>(results.begin(), results.end());
}
int countPairs(vector<int>& nums) {
unordered_map<int, int> count;
int result = 0;
for (int num : nums) {
vector<int> transforms = getTransforms(num);
for (int t : transforms) {
if (count.find(t) != count.end()) {
result += count[t];
}
}
count[num]++;
}
return result;
}
};
class Solution:
def getTransforms(self, num):
s = str(num)
results = set()
# 0次交换
results.add(num)
# 1次交换
for i in range(len(s)):
for j in range(i + 1, len(s)):
temp = list(s)
temp[i], temp[j] = temp[j], temp[i]
results.add(int(''.join(temp)))
# 2次交换
for i in range(len(s)):
for j in range(i + 1, len(s)):
temp = list(s)
temp[i], temp[j] = temp[j], temp[i]
for k in range(len(temp)):
for l in range(k + 1, len(temp)):
temp2 = temp[:]
temp2[k], temp2[l] = temp2[l], temp2[k]
results.add(int(''.join(temp2)))
return list(results)
def countPairs(self, nums: List[int]) -> int:
count = {}
result = 0
for num in nums:
transforms = self.getTransforms(num)
for t in transforms:
if t in count:
result += count[t]
count[num] = count.get(num, 0) + 1
return result
public class Solution {
private List<int> GetTransforms(int num) {
string s = num.ToString();
HashSet<int> results = new HashSet<int>();
// 0次交换
results.Add(num);
// 1次交换
for (int i = 0; i < s.Length; i++) {
for (int j = i + 1; j < s.Length; j++) {
char[] temp = s.ToCharArray();
(temp[i], temp[j]) = (temp[j], temp[i]);
results.Add(int.Parse(new string(temp)));
}
}
// 2次交换
for (int i = 0; i < s.Length; i++) {
for (int j = i + 1; j < s.Length; j++) {
char[] temp = s.ToCharArray();
(temp[i], temp[j]) = (temp[j], temp[i]);
for (int k = 0; k < temp.Length; k++) {
for (int l = k + 1; l < temp.Length; l++) {
char[] temp2 = (char[])temp.Clone();
(temp2[k], temp2[l]) = (temp2[l], temp2[k]);
results.Add(int.Parse(new string(temp2)));
}
}
}
}
return new List<int>(results);
}
public int CountPairs(int[] nums) {
Dictionary<int, int> count = new Dictionary<int, int>();
int result = 0;
foreach (int num in nums) {
List<int> transforms = GetTransforms(num);
foreach (int t in transforms) {
if (count.ContainsKey(t)) {
result += count[t];
}
}
count[num] = count.GetValueOrDefault(num, 0) + 1;
}
return result;
}
}
var countPairs = function(nums) {
const getTransforms = (num) => {
const s = num.toString();
const results = new Set();
// 0次交换
results.add(num);
// 1次交换
for (let i = 0; i < s.length; i++) {
for (let j = i + 1; j < s.length; j++) {
const temp = s.split('');
[temp[i], temp[j]] = [temp[j], temp[i]];
results.add(parseInt(temp.join('')));
}
}
// 2次交换
for (let i = 0; i < s.length; i++) {
for (let j = i + 1; j < s.length; j++) {
const temp = s.split('');
[temp[i], temp[j]] = [temp[j], temp[i]];
for (let k = 0; k < temp.length; k++) {
for (let l = k + 1; l < temp.length; l++) {
const temp2 = [...temp];
[temp2[k], temp2[l]] = [temp2[l], temp2[k]];
results.add(parseInt(temp2.join('')));
}
}
}
}
return Array.from(results);
};
const count = new Map();
let result = 0;
for (const num of nums) {
const transforms = getTransforms(num);
for (const t of transforms) {
if (count.has(t)) {
result += count.get(t);
}
}
count.set(num, (count.get(num) || 0) + 1);
}
return result;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n × d⁴) | 其中 n 是数组长度，d 是数字的最大位数。对每个数字生成所有变换需要 O(d⁴) 时间 |
| 空间复杂度 | O(n × d⁴) | 存储所有可能的变换结果和哈希表 |