公司网站开发的核心技术,没有装wordpress,珠宝网站建商台北,移动网站建设初学视频教程题目描述#xff1a;
给你一个整数数组 nums 。
如果一组数字 (i,j) 满足 nums[i] nums[j] 且 i j #xff0c;就可以认为这是一组 好数对 。
返回好数对的数目。 示例 1#xff1a; 输入#xff1a;nums [1,2,3,1,1,3]
输出#xff1a;4
解释#xff1a;有 4 …题目描述
给你一个整数数组 nums 。
如果一组数字 (i,j) 满足 nums[i] nums[j] 且 i j 就可以认为这是一组 好数对 。
返回好数对的数目。 示例 1 输入nums [1,2,3,1,1,3]
输出4
解释有 4 组好数对分别是 (0,3), (0,4), (3,4), (2,5) 下标从 0 开始示例 2 输入nums [1,1,1,1]
输出6
解释数组中的每组数字都是好数对 示例 3 输入nums [1,2,3]
输出0提示 1 nums.length 1001 nums[i] 100 代码实现
方法一可以通过暴力枚举的方式来求解。可以使用两个嵌套的循环外层循环枚举所有可能的位置 i内层循环枚举 i 后面的位置 j如果 nums[i] nums[j]则说明找到了一组好数对累加计数器即可。
public int numIdenticalPairs(int[] nums) {int n nums.length;int count 0;for (int i 0; i n; i) {for (int j i 1; j n; j) {if (nums[i] nums[j]) {count;}}}return count;
}该方法的时间复杂度为 O(n^2)空间复杂度为 O(1)。 方法二可以利用哈希表来记录每个数字出现的次数。
具体步骤如下
创建一个哈希表 map用于记录数组中每个数字出现的次数。遍历数组 nums对于每个数字 num将其在哈希表中对应的计数器加一。遍历哈希表 map对于每个数字出现的次数 count好数对的数量为 count * (count - 1) / 2将其累加到结果 ans 中。返回结果 ans。
public int numIdenticalPairs(int[] nums) {MapInteger, Integer map new HashMap();int count 0;for (int num : nums) {map.put(num, map.getOrDefault(num, 0) 1);}for (int num : map.keySet()) {int freq map.get(num);count freq * (freq - 1) / 2;}return count;
}这种方法的时间复杂度为 O(n)其中 n 是数组 nums 的长度。需要遍历两次数组第一次遍历统计每个数字出现的次数第二次遍历计算好数对的数量。空间复杂度为 O(n)用于存储哈希表。相较于暴力枚举的方法这种方法的效率更高。
第二种方法不是很能理解O.o... count freq * (freq - 1) / 2; 这句代码的作用是计算出当前数字 num 的好数对数量并将其累加到变量 count 上。
具体来说如果一个数字在数组中出现了 freq 次那么它可以组成的好数对数量为 freq * (freq - 1) / 2。这个公式的解释如下
假设这个数字出现在数组中的位置分别为 i1, i2, ..., ifreq那么它可以和其他数字组成的好数对数量就是 C(freq, 2) freq! / (2! * (freq - 2)!) freq * (freq - 1) / 2 其中 C(n, m) 表示从 n 个元素中选取 m 个元素的组合数。
因为一个数字出现 freq 次所以它可以和其他任意一个相同的数字组成一组好数对因此它能够组成的好数对数量就是 C(freq, 2)。
最后我们遍历哈希表中的每个数字将它们的好数对数量相加得到总的好数对数量即为变量 count 的值。
总之这句代码的作用是将当前数字能够组成的好数对数量累加到计数器上。
