题目描述
注意：在这个问题中，操作次数增加为至多 两次 。
给你一个正整数数组 nums 。
如果我们执行以下操作 至多两次 可以让两个整数 x 和 y 相等，那么我们称这个数对是 近似相等 的：
- 选择
x 或者 y 之一，将这个数字中的两个数位交换。
请你返回 nums 中，下标 i 和 j 满足 i < j 且 nums[i] 和 nums[j] 近似相等 的数对数目。
注意 ，执行操作后得到的整数可以有前导 0 。
示例 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 中数位 1 和从左往右的第二个 0 ，得到 001 ，也就是 1 。
- 10 和 100 。交换 100 中数位 1 和从左往右的第一个 0 ，得到 010 ，也就是 10 。
提示：
2 <= nums.length <= 50001 <= nums[i] < 107
解法
方法一：排序 + 枚举
我们可以枚举每一个数，然后对于每一个数，我们可以枚举每一对不同的数位，然后交换这两个数位，得到一个新的数，记录到一个哈希表 $\textit{vis}$ 中，表示这个数至多进行一次交换后的所有可能的数，然后继续枚举每一对不同的数位，交换这两个数位，得到一个新的数，记录到哈希表 $\textit{vis}$ 中，表示这个数至多进行两次交换后的所有可能的数。
这样枚举，会少统计一些数对，比如 $[100, 1]$，因为 $100$ 交换后的数是 $1$，而此前枚举过数不包含 $1$，因此会少统计一些数对。我们只需要在枚举之前，将数组排序，即可解决这个问题。
时间复杂度 $O(n \times (\log n + \log^5 M))$，空间复杂度 $O(n + \log^4 M)$。其中 $n$ 是数组 $\textit{nums}$ 的长度，而 $M$ 是数组 $\textit{nums}$ 中的最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution:
def countPairs(self, nums: List[int]) -> int:
nums.sort()
ans = 0
cnt = defaultdict(int)
for x in nums:
vis = {x}
s = list(str(x))
m = len(s)
for j in range(m):
for i in range(j):
s[i], s[j] = s[j], s[i]
vis.add(int("".join(s)))
for q in range(i + 1, m):
for p in range(i + 1, q):
s[p], s[q] = s[q], s[p]
vis.add(int("".join(s)))
s[p], s[q] = s[q], s[p]
s[i], s[j] = s[j], s[i]
ans += sum(cnt[x] for x in vis)
cnt[x] += 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 | class Solution {
public int countPairs(int[] nums) {
Arrays.sort(nums);
int ans = 0;
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : nums) {
Set<Integer> vis = new HashSet<>();
vis.add(x);
char[] s = String.valueOf(x).toCharArray();
for (int j = 0; j < s.length; ++j) {
for (int i = 0; i < j; ++i) {
swap(s, i, j);
vis.add(Integer.parseInt(String.valueOf(s)));
for (int q = i; q < s.length; ++q) {
for (int p = i; p < q; ++p) {
swap(s, p, q);
vis.add(Integer.parseInt(String.valueOf(s)));
swap(s, p, q);
}
}
swap(s, i, j);
}
}
for (int y : vis) {
ans += cnt.getOrDefault(y, 0);
}
cnt.merge(x, 1, Integer::sum);
}
return ans;
}
private void swap(char[] s, int i, int j) {
char t = s[i];
s[i] = s[j];
s[j] = t;
}
}
|
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 | class Solution {
public:
int countPairs(vector<int>& nums) {
sort(nums.begin(), nums.end());
int ans = 0;
unordered_map<int, int> cnt;
for (int x : nums) {
unordered_set<int> vis = {x};
string s = to_string(x);
for (int j = 0; j < s.length(); ++j) {
for (int i = 0; i < j; ++i) {
swap(s[i], s[j]);
vis.insert(stoi(s));
for (int q = i + 1; q < s.length(); ++q) {
for (int p = i + 1; p < q; ++p) {
swap(s[p], s[q]);
vis.insert(stoi(s));
swap(s[p], s[q]);
}
}
swap(s[i], s[j]);
}
}
for (int y : vis) {
ans += cnt[y];
}
cnt[x]++;
}
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 | func countPairs(nums []int) (ans int) {
sort.Ints(nums)
cnt := make(map[int]int)
for _, x := range nums {
vis := make(map[int]struct{})
vis[x] = struct{}{}
s := []rune(strconv.Itoa(x))
for j := 0; j < len(s); j++ {
for i := 0; i < j; i++ {
s[i], s[j] = s[j], s[i]
y, _ := strconv.Atoi(string(s))
vis[y] = struct{}{}
for q := i + 1; q < len(s); q++ {
for p := i + 1; p < q; p++ {
s[p], s[q] = s[q], s[p]
z, _ := strconv.Atoi(string(s))
vis[z] = struct{}{}
s[p], s[q] = s[q], s[p]
}
}
s[i], s[j] = s[j], s[i]
}
}
for y := range vis {
ans += cnt[y]
}
cnt[x]++
}
return
}
|
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 | function countPairs(nums: number[]): number {
nums.sort((a, b) => a - b);
let ans = 0;
const cnt = new Map<number, number>();
for (const x of nums) {
const vis = new Set<number>();
vis.add(x);
const s = x.toString().split('');
for (let j = 0; j < s.length; j++) {
for (let i = 0; i < j; i++) {
[s[i], s[j]] = [s[j], s[i]];
vis.add(+s.join(''));
for (let q = i + 1; q < s.length; ++q) {
for (let p = i + 1; p < q; ++p) {
[s[p], s[q]] = [s[q], s[p]];
vis.add(+s.join(''));
[s[p], s[q]] = [s[q], s[p]];
}
}
[s[i], s[j]] = [s[j], s[i]];
}
}
for (const y of vis) {
ans += cnt.get(y) || 0;
}
cnt.set(x, (cnt.get(x) || 0) + 1);
}
return ans;
}
|