良いペアの数Leetcodeソリューション


難易度 簡単に
よく聞かれる Amazon (アマゾン) マイクロソフト
配列 ハッシング 数学

問題文

この問題では、整数の配列が与えられ、a [i] = a [j]である良いペア​​(a [i]、a [j])の総数を見つける必要があります。

nums = [1,2,3,1,1,3]
4

説明:インデックス(4)、(0,3)、(0,4)、(3,4)に2,5つの適切なペアがあります。

[1,1,1,1]
6

説明:アレイ内の各ペアは正常です。

アプローチ(ブルートフォース)

与えられた問題では、XNUMXつのループを使用できます。XNUMXつはペアのa [i]に、もうXNUMXつはa [j]に使用します。 これで ネストされたループ ペア(a [i]、a [j])のすべての可能な組み合わせを繰り返し、a [i]がa [j]と等しいかどうかを確認します。

アルゴリズム:

1.カウント変数を作成し、ゼロで初期化します。
2.ネストされたループを実行します。a[i]の外側のループはi = 0からi = n-1まで、内側のループはa [j]のj = i +1からj = n-1までです。
3. a [i] = a [j]の場合、値を1ずつ増やして、現在のペアをカウントに追加します。
4.カウント変数の値を返します。

グッドペア数の実装Leetcodeソリューション

C ++プログラム

#include <bits/stdc++.h>
using namespace std;

int numIdenticalPairs(vector<int>& nums) 
{
       int res = 0;
       for(int i=0;i<nums.size();i++)
           for(int j=i+1;j<nums.size();j++)
               if(nums[i]==nums[j]) res++;
               
       return res;
}

int main() 
{
    vector<int> nums={1,2,3,1,1,3};
  
  cout<<numIdenticalPairs(nums)<<endl;

  return 0; 
}
4

Javaプログラム

import java.lang.*;

class GoodPairs
{  
    public static int numIdenticalPairs(int[] nums) 
    {
        int res = 0;
        for(int i=0;i<nums.length;i++)
          for(int j=i+1;j<nums.length;j++)
             if(nums[i]==nums[j])   res++;

        return res;
    }

    public static void main(String args[])
    {
       int nums[]={1,2,3,1,1,3};
  
       System.out.println( numIdenticalPairs(nums));
        
    }
}
4

良いペアの数の複雑さの分析Leetcodeソリューション

時間の複雑さ

O(N ^ 2): ここで、Nは指定された配列のサイズです。 2つのループを使用し、インデックスiとjの要素のすべての組み合わせをチェックしているため、時間計算量はO(N ^ XNUMX)になります。

スペースの複雑さ 

O(1): 余分なメモリは使用していません。

 

アプローチ(最適化)

を使用してソリューションを最適化できます ハッシュマップ。 ペアのすべての組み合わせをi * j回繰り返す必要はありません。 等しい要素だけを数える必要があります。
つまり、配列内の特定の要素の数がある場合、この類似した要素のセット内の任意のXNUMXつの要素を選択する方法の総数を計算できます。
このためにできることは、最初の要素から繰り返し、すべてのステップで各要素の数を更新することです。
要素が見つかるたびに、カウントマップ変数を使用して、この要素の前にすでに存在する同様の要素の数を確認します。 以前に発生したすべての要素とペアになることができるようにします。
そのカウントを結果に追加し、現在の要素のカウントを+1更新(インクリメント)します。

良いペアの数Leetcodeソリューション

アルゴリズム:
1.キーが要素で値がその要素の現在のカウントである整数と整数のHasマップを作成します。
2. i = 0からn-1までの各要素に対してforループを実行します。
3.マップに配置する前にcount(a [i])を見つけ、この値をresに追加します。
4.ここで、a [i]のカウントをcount(a [i])= count(a [i])+ 1として更新します。
5.resの値を返します。

グッドペア数の実装Leetcodeソリューション

C ++プログラム

#include <bits/stdc++.h>
using namespace std;

int numIdenticalPairs(vector<int>& nums) 
{
    int res = 0;
    unordered_map<int, int> count;
    for (int a: nums) 
    {
        res += count[a]++;
    }
  
    return res;
}

int main() 
{
    vector<int> nums={1,2,3,1,1,3};
  
  cout<<numIdenticalPairs(nums)<<endl;

  return 0; 
}
4

Javaプログラム

import java.lang.*;
import java.util.*;

class GoodPairs
{  
    public static int numIdenticalPairs(int[] nums) 
    {
        int res = 0;
        Map<Integer,Integer> count= new HashMap<Integer,Integer>();
        for (int a: nums)
        {
            int cur=count.getOrDefault(a,0);
            res += cur;
            count.put(a,cur+1);
        }
        return res;
    }

    public static void main(String args[])
    {
       int nums[]={1,2,3,1,1,3};
  
       System.out.println( numIdenticalPairs(nums));
        
    }
}
4

良いペアの数の複雑さの分析Leetcodeソリューション

時間の複雑さ

オン) : ハッシュマップを使用して各要素のカウントを更新する作業を継続的に行っているため、時間計算量はO(N)になります。

スペースの複雑さ 

オン) :ハッシュマップを使用して、各一意の要素の数を保存しています。 最悪の場合、N個の異なる要素が存在する可能性があります。