class Solution {
public:
int countPairs(vector<int>& nums) {
}
};
3267. 统计近似相等数对 II
注意：在这个问题中，操作次数增加为至多 两次 。
给你一个正整数数组 nums 。
如果我们执行以下操作 至多两次 可以让两个整数 x 和 y 相等，那么我们称这个数对是 近似相等 的：
x 或者 y 之一，将这个数字中的两个数位交换。请你返回 nums 中，下标 i 和 j 满足 i < j 且 nums[i] 和 nums[j] 近似相等 的数对数目。
注意 ，执行操作后得到的整数可以有前导 0 。
示例 1：
输入：nums = [1023,2310,2130,213]
输出：4
解释：
近似相等数对包括：
示例 2：
输入：nums = [1,10,100]
输出：3
解释：
近似相等数对包括：
提示：
2 <= nums.length <= 50001 <= nums[i] < 107原站题解
cpp 解法, 执行用时: 1280 ms, 内存消耗: 335.9 MB, 提交时间: 2024-08-26 10:03:47
const int POW10[7] = {1, 10, 100, 1000, 10000, 100000, 1000000};
class Solution {
public:
int countPairs(vector<int>& nums) {
ranges::sort(nums);
int ans = 0, a[7];
unordered_map<int, int> cnt;
for (int x : nums) {
unordered_set<int> st = {x}; // 不交换
int m = 0;
for (int v = x; v; v /= 10) {
a[m++] = v % 10;
}
for (int i = 0; i < m; i++) {
for (int j = i + 1; j < m; j++) {
if (a[i] == a[j]) { // 小优化
continue;
}
int y = x + (a[j] - a[i]) * (POW10[i] - POW10[j]);
st.insert(y); // 交换一次
swap(a[i], a[j]);
for (int p = i + 1; p < m; p++) {
for (int q = p + 1; q < m; q++) {
st.insert(y + (a[q] - a[p]) * (POW10[p] - POW10[q])); // 交换两次
}
}
swap(a[i], a[j]);
}
}
for (int v : st) {
ans += cnt.contains(v) ? cnt[v] : 0;
}
cnt[x]++;
}
return ans;
}
};
java 解法, 执行用时: 279 ms, 内存消耗: 44.6 MB, 提交时间: 2024-08-26 10:03:23
class Solution {
private static final int[] POW10 = {1, 10, 100, 1000, 10000, 100000, 1000000};
public int countPairs(int[] nums) {
Arrays.sort(nums);
int ans = 0;
Map<Integer, Integer> cnt = new HashMap<>();
int[] a = new int[7];
for (int x : nums) {
Set<Integer> vis = new HashSet<>();
vis.add(x); // 不交换
ans += cnt.getOrDefault(x, 0);
int m = 0;
for (int v = x; v > 0; v /= 10) {
a[m++] = v % 10;
}
for (int i = 0; i < m; i++) {
for (int j = i + 1; j < m; j++) {
if (a[i] == a[j]) { // 小优化
continue;
}
int y = x + (a[j] - a[i]) * (POW10[i] - POW10[j]);
if (vis.add(y)) {
ans += cnt.getOrDefault(y, 0); // 交换一次
}
swap(a, i, j);
for (int p = i + 1; p < m; p++) {
for (int q = p + 1; q < m; q++) {
int z = y + (a[q] - a[p]) * (POW10[p] - POW10[q]);
if (vis.add(z)) {
ans += cnt.getOrDefault(z, 0); // 交换两次
}
}
}
swap(a, i, j);
}
}
cnt.merge(x, 1, Integer::sum);
}
return ans;
}
private void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
golang 解法, 执行用时: 517 ms, 内存消耗: 7.4 MB, 提交时间: 2024-08-26 10:02:59
var pow10 = [...]int{1, 10, 100, 1000, 10000, 100000, 1000000}
func countPairs(nums []int) int {
slices.Sort(nums)
ans := 0
cnt := make(map[int]int)
a := [len(pow10)]int{}
for _, x := range nums {
st := map[int]struct{}{x: {}} // 不交换
m := 0
for v := x; v > 0; v /= 10 {
a[m] = v % 10
m++
}
for i := 0; i < m; i++ {
for j := i + 1; j < m; j++ {
if a[i] == a[j] { // 小优化
continue
}
y := x + (a[j]-a[i])*(pow10[i]-pow10[j])
st[y] = struct{}{} // 交换一次
a[i], a[j] = a[j], a[i]
for p := i + 1; p < m; p++ {
for q := p + 1; q < m; q++ {
st[y+(a[q]-a[p])*(pow10[p]-pow10[q])] = struct{}{} // 交换两次
}
}
a[i], a[j] = a[j], a[i]
}
}
for x := range st {
ans += cnt[x]
}
cnt[x]++
}
return ans
}
python3 解法, 执行用时: 1255 ms, 内存消耗: 18.1 MB, 提交时间: 2024-08-26 10:02:44
POW10 = [10 ** i for i in range(7)]
class Solution:
def countPairs(self, nums: List[int]) -> int:
nums.sort()
ans = 0
cnt = defaultdict(int)
for x in nums:
st = {x} # 不交换
a = list(map(int, str(x)))[::-1]
m = len(a)
for i in range(m):
for j in range(i + 1, m):
if a[i] == a[j]: # 小优化
continue
y = x + (a[j] - a[i]) * (POW10[i] - POW10[j])
st.add(y) # 交换一次
a[i], a[j] = a[j], a[i]
for p in range(i + 1, m):
for q in range(p + 1, m):
st.add(y + (a[q] - a[p]) * (POW10[p] - POW10[q])) # 交换两次
a[i], a[j] = a[j], a[i]
ans += sum(cnt[v] for v in st)
cnt[x] += 1
return ans
golang 解法, 执行用时: 481 ms, 内存消耗: 7 MB, 提交时间: 2024-08-26 10:02:04
func countPairs(nums []int) (ans int) {
slices.Sort(nums)
cnt := map[int]int{}
for _, x := range nums {
set := map[int]struct{}{x: {}} // 不交换
s := []byte(strconv.Itoa(x))
m := len(s)
for i := range s {
for j := i + 1; j < m; j++ {
s[i], s[j] = s[j], s[i]
set[atoi(s)] = struct{}{} // 交换一次
for p := i + 1; p < m; p++ {
for q := p + 1; q < m; q++ {
s[p], s[q] = s[q], s[p]
set[atoi(s)] = struct{}{} // 交换两次
s[p], s[q] = s[q], s[p]
}
}
s[i], s[j] = s[j], s[i]
}
}
for x := range set {
ans += cnt[x]
}
cnt[x]++
}
return
}
// 手动转 int 快一些
func atoi(s []byte) (res int) {
for _, b := range s {
res = res*10 + int(b&15)
}
return
}