跳到主要内容

1512. 好数对的数目 [easy]

1512. 好数对的数目 [easy]​

https://leetcode-cn.com/problems/number-of-good-pairs/

给你一个整数数组 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

通过次数7,331 | 提交次数8,205

Second Try​

2020-07-15

暴力写法，这也能行。

冒泡写法中，可以实现i != j, 并且(i, j)的逆配对(j，i)不会再次出现，刚好符合这题目的要求。

class Solution(object):
    def numIdenticalPairs(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        rv = 0 
        for i in range(0, len(nums)- 1):
            for j in range(i + 1, len(nums)):
                if nums[i] == nums[j]:
                    rv += 1
        return rv
  • 执行用时：16 ms, 在所有 Python 提交中击败了88.24%的用户
  • 内存消耗：12.9 MB, 在所有 Python 提交中击败了100.00%的用户

First Try​

2020-07-12

统计相等的次数，然后用组合算法C(n,2)即可。 

class Solution(object):
    def numIdenticalPairs(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        counter = collections.defaultdict(int)
        for n in nums:
            counter[n] += 1
        rv = 0 
        for k, v in counter.items():
            if v > 1:
                rv += (math.factorial(v) / (math.factorial(v - 2) * 2))
        return rv
  • 执行用时：24 ms, 在所有 Python 提交中击败了48.24%的用户
  • 内存消耗：12.9 MB, 在所有 Python 提交中击败了100.00%的用户