当前位置:   article > 正文

力扣(LeetCode)-1512. 好数对的数目_给你一个整数数组 nums 。 如果一组数字 (i,j) 满足 nums[i] == nums[j]

给你一个整数数组 nums 。 如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j

给你一个整数数组 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 <= 100
1 <= nums[i] <= 100

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-of-good-pairs
题解:

首先想到的是双循环暴力计数就行,时间复杂度为O(n^2)

  1. class Solution {
  2. public int numIdenticalPairs(int[] nums) {
  3. int count = 0;
  4. for(int i = 0;i < nums.length;i++){
  5. for(int j = i + 1;j < nums.length;j++){
  6. if(nums[i] == nums[j]){
  7. count++;
  8. }
  9. }
  10. }
  11. return count;
  12. }
  13. }

官方给出了另外一种解法,先找到元素相同的个数(记为v),同时要保证i<j,根据排列的思想就会找到v(v-1)/2种,例如nums = [1,2,3,1,1,3],以元素1为例,v=3,好对数的数量为2+1。

  1. class Solution {
  2. public int numIdenticalPairs(int[] nums) {
  3. int count = 0;
  4. // 存储元素出现的次数
  5. Map<Integer, Integer> m = new HashMap<Integer, Integer>();
  6. for(int i = 0;i < nums.length;i++){
  7. m.put(nums[i],m.getOrDefault(nums[i], 0) + 1);
  8. }
  9. for (Map.Entry<Integer, Integer> entry : m.entrySet()) {
  10. int v = entry.getValue();
  11. count += v * (v - 1) / 2;
  12. }
  13. return count;
  14. }
  15. }

 看了别人的代码看到了一种有意思的解法,只有一句666。不用再次遍历map,如果这个数第一次出现,这个数的好对数为0,value更改为1,下一次这个数出现时,这个数的好对数就位0+1,value更改为2,一次类推,不同的数的好对数都会被计算。

  1. class Solution {
  2. public int numIdenticalPairs(int[] nums) {
  3. int count=0;
  4. Map<Integer,Integer> map=new HashMap<>();
  5. for(int num:nums){
  6. int value=map.getOrDefault(num,0);
  7. count+=value;
  8. map.put(num,valve+1);
  9. }
  10. return count;
  11. }
  12. }

 另一种解法,不使用map:利用数组统计元素出现个数的统计过程,计算好对数的个数

  1. class Solution {
  2. public int numIdenticalPairs(int[] nums) {
  3. int count=0;
  4. //因为 1<= nums[i] <= 100 所以申请大小为100的数组
  5. //temp用来记录num的个数
  6. int[] temp = new int[100];
  7. /*
  8. 从前面开始遍历nums
  9. 假设nums = [1,1,1,1]
  10. 第一遍
  11. temp是[0,0,0,0]
  12. count+=0;
  13. temp[0]++;
  14. 第二遍
  15. temp是[1,0,0,0]
  16. count+=1;
  17. temp[0]++;
  18. 第三遍
  19. temp=[2,0,0,0]
  20. count+=2;
  21. temp[0]++;
  22. 第四遍
  23. temp=[3,0,0,0]
  24. count+=3;
  25. temp[0]++;
  26. */
  27. for (int num : nums) {
  28. /*
  29. 这行代码可以写成
  30. count+=temp[num - 1];
  31. temp[num - 1]++;
  32. */
  33. count += temp[num - 1]++;
  34. }
  35. return count;
  36. }
  37. }

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小舞很执着/article/detail/765876
推荐阅读
相关标签
  

闽ICP备14008679号