3267. Count Almost Equal Pairs II
Description
Attention: In this version, the number of operations that can be performed, has been increased to twice.
You are given an array nums
consisting of positive integers.
We call two integers x
and y
almost equal if both integers can become equal after performing the following operation at most twice:
- Choose either
x
ory
and swap any two digits within the chosen number.
Return the number of indices i
and j
in nums
where i < j
such that nums[i]
and nums[j]
are almost equal.
Note that it is allowed for an integer to have leading zeros after performing an operation.
Example 1:
Input: nums = [1023,2310,2130,213]
Output: 4
Explanation:
The almost equal pairs of elements are:
- 1023 and 2310. By swapping the digits 1 and 2, and then the digits 0 and 3 in 1023, you get 2310.
- 1023 and 213. By swapping the digits 1 and 0, and then the digits 1 and 2 in 1023, you get 0213, which is 213.
- 2310 and 213. By swapping the digits 2 and 0, and then the digits 3 and 2 in 2310, you get 0213, which is 213.
- 2310 and 2130. By swapping the digits 3 and 1 in 2310, you get 2130.
Example 2:
Input: nums = [1,10,100]
Output: 3
Explanation:
The almost equal pairs of elements are:
- 1 and 10. By swapping the digits 1 and 0 in 10, you get 01 which is 1.
- 1 and 100. By swapping the second 0 with the digit 1 in 100, you get 001, which is 1.
- 10 and 100. By swapping the first 0 with the digit 1 in 100, you get 010, which is 10.
Constraints:
2 <= nums.length <= 5000
1 <= nums[i] < 107
Solutions
Solution 1: Sorting + Enumeration
We can enumerate each number, and for each number, we can enumerate each pair of different digits, then swap these two digits to get a new number. Record this new number in a hash table $\textit{vis}$, representing all possible numbers after at most one swap. Then continue to enumerate each pair of different digits, swap these two digits to get a new number, and record it in the hash table $\textit{vis}$, representing all possible numbers after at most two swaps.
This enumeration may miss some pairs of numbers, such as $[100, 1]$, because the number obtained after swapping $100$ is $1$, and the previously enumerated numbers do not include $1$, so some pairs of numbers will be missed. We only need to sort the array before enumeration to solve this problem.
The time complexity is $O(n \times (\log n + \log^5 M))$, and the space complexity is $O(n + \log^4 M)$. Here, $n$ is the length of the array $\textit{nums}$, and $M$ is the maximum value in the array $\textit{nums}$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
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 |
|
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 |
|