美丽下标对的数目
难度:
标签:
题目描述
You are given a 0-indexed integer array nums. A pair of indices i, j where 0 <= i < j < nums.length is called beautiful if the first digit of nums[i] and the last digit of nums[j] are coprime.
Return the total number of beautiful pairs in nums.
Two integers x and y are coprime if there is no integer greater than 1 that divides both of them. In other words, x and y are coprime if gcd(x, y) == 1, where gcd(x, y) is the greatest common divisor of x and y.
Example 1:
Input: nums = [2,5,1,4] Output: 5 Explanation: There are 5 beautiful pairs in nums: When i = 0 and j = 1: the first digit of nums[0] is 2, and the last digit of nums[1] is 5. We can confirm that 2 and 5 are coprime, since gcd(2,5) == 1. When i = 0 and j = 2: the first digit of nums[0] is 2, and the last digit of nums[2] is 1. Indeed, gcd(2,1) == 1. When i = 1 and j = 2: the first digit of nums[1] is 5, and the last digit of nums[2] is 1. Indeed, gcd(5,1) == 1. When i = 1 and j = 3: the first digit of nums[1] is 5, and the last digit of nums[3] is 4. Indeed, gcd(5,4) == 1. When i = 2 and j = 3: the first digit of nums[2] is 1, and the last digit of nums[3] is 4. Indeed, gcd(1,4) == 1. Thus, we return 5.
Example 2:
Input: nums = [11,21,12] Output: 2 Explanation: There are 2 beautiful pairs: When i = 0 and j = 1: the first digit of nums[0] is 1, and the last digit of nums[1] is 1. Indeed, gcd(1,1) == 1. When i = 0 and j = 2: the first digit of nums[0] is 1, and the last digit of nums[2] is 2. Indeed, gcd(1,2) == 1. Thus, we return 2.
Constraints:
2 <= nums.length <= 1001 <= nums[i] <= 9999nums[i] % 10 != 0
代码结果
运行时间: 69 ms, 内存: 16.1 MB
/*
* 题目思路：
* 1. 使用 Java Stream API 对数组中的所有下标对 (i, j) 进行遍历。
* 2. 通过过滤器保留满足 i < j 的下标对。
* 3. 对于每对 (i, j)，获取 nums[i] 的第一个数字和 nums[j] 的最后一个数字。
* 4. 判断这两个数字是否互质，即它们的最大公约数 (GCD) 是否为 1。
* 5. 计数并返回美丽下标对的总数。
*/
import java.util.stream.*;
public class BeautifulPairsStream {
public int countBeautifulPairs(int[] nums) {
return (int) IntStream.range(0, nums.length)
.boxed()
.flatMap(i -> IntStream.range(i + 1, nums.length)
.mapToObj(j -> new int[] {i, j}))
.filter(pair -> gcd(getFirstDigit(nums[pair[0]]), getLastDigit(nums[pair[1]])) == 1)
.count();
}
private int getFirstDigit(int num) {
while (num >= 10) {
num /= 10;
}
return num;
}
private int getLastDigit(int num) {
return num % 10;
}
private int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public static void main(String[] args) {
BeautifulPairsStream bp = new BeautifulPairsStream();
int[] nums1 = {2, 5, 1, 4};
int[] nums2 = {11, 21, 12};
System.out.println(bp.countBeautifulPairs(nums1)); // Output: 5
System.out.println(bp.countBeautifulPairs(nums2)); // Output: 2
}
}
解释
方法:
题解采用了计数排序和贪心的方法来高效处理美丽下标对的统计。首先，创建了一个大小为10的数组cnt，用来计数每个数字（1到9）作为第一个数字出现的次数。对于nums中的每个元素x，首先判断其最后一个数字（x%10）与已统计的第一个数字是否互质，如果互质，则增加对应的cnt[y]值到结果ans中，这样确保了不重复统计下标对。然后，通过不断除以10将x缩小，直到x小于10，此时x就是该数字的第一个数字，对应的cnt[x]增加1，用于后续的配对统计。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么选择使用计数排序而不是其他排序方法来处理这个问题？
▷🦆
在解题中，使用了`cnt[y] and gcd(x % 10, y) == 1`来判断互质条件，这种方法在所有情况下都是有效的吗？存在哪些潜在的计算错误或遗漏？
▷🦆
代码中对数字的处理方式是`while x >= 10: x //= 10`，这样处理对所有输入的数字都有效吗？如果输入的数字中有0怎么办？
▷🦆
题解中的循环`for y in range(1, 10)`是基于哪些考虑？这是否意味着所有输入的nums元素的第一个数字必定在1到9之间？
▷