समांतर डॉमिनो पेअर्सची संख्या लीटकोड सोल्यूशन


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन
अरे

समस्या विधान

समतुल्य डोमिनोज जोडींची संख्या ”या समस्येमध्ये आम्हाला डोमिनोजची एक यादी देण्यात आली आहे जिथे प्रत्येक डोमिनोजमध्ये डोमिनोज सारख्या दोन मूल्यांचा समावेश असतो [i] = [ए, बी]. दोन डोमिनोज, डोमिनोज [i] = [ए, बी] आणि डोमिनोज [जे] = [सी, डी] समतुल्य असल्यास (अ == डी आणि बी == डी) किंवा (ए == डी आणि सी == डी) .

समांतर डॉमिनो पेअर्सची संख्या लीटकोड सोल्यूशन

आमचे कार्य म्हणजे जोडीची एकूण संख्या (i, j) शोधणे जिथे मी! = J आणि डोमिनोज [i] आहेत समतुल्य डोमिनोज [जे] करण्यासाठी. अ आणि बीची दिलेली मूल्ये [1,9] श्रेणीमध्ये आहेत.

उदाहरण

dominoes = [[1,2],[2,1],[3,4],[5,6]]
1

स्पष्टीकरण: या उदाहरणात डोमिनोज [0] डोमिनोज समतुल्य आहे [1] कारण ते अट संतुष्ट करते (अ == डी आणि सी == डी). समतुल्य डोमिनोज मापदंडांचे समाधान करणारी ही एकमेव जोडी आहे म्हणूनच उत्तर एक आहे.

समतुल्य डोमिनोज पेअर्स लीटकोड सोल्यूशनच्या संख्येसाठी दृष्टिकोण

आम्ही डोमिनो निवडून आणि नंतर निवडलेल्या डोमिनोजी समतुल्य असल्यास इतर उर्वरित डोमिनोज तपासून ही समस्या सोडवू शकतो. आम्ही हे सर्व डोमिनोजसाठी करू आणि नंतर समांतर डॉमिनोजींची एकूण संख्या 2 ने विभाजित करू तर उत्तर मिळेल. परंतु या पध्दतीची वेळ जटिलता ओ (एन * एन) असेल. आम्ही ओ (एन) वेळेत ही समस्या खालील चरणांचे अनुसरण करुन सोडवू शकतो.

  1. आम्ही दोन संख्या (अ, बी) एकाच संख्येमध्ये रूपांतरित करू, यामुळे समांतरता तपासणे सोपे होईल.
  2. हे हॅश फंक्शन दोन नंबरला एका क्रमांकामध्ये c = मि (अ, बी) * १० + कमाल (अ, बी) मध्ये रूपांतरित करेल.
  3. आता आम्ही प्रत्येक संख्येची वारंवारिता मोजण्यासाठी हॅश टेबल बनवू.
  4. आपण डोमिनोज अ‍ॅरे मागे टाकू आणि हॅश टेबल मध्ये c ची वारंवारिता संचित करू.
  5. सी व्हॅल्यूजची वारंवारता मोजल्यानंतर आपण समांतर डॉमिनोजची संख्या काढू शकतो. समजा x हॅश टेबलमध्ये एक्स चे f वारंवारता असेल तर व्हॅल्यू x साठी समकक्ष जोड्यांची संख्या fC2 असेल (f * (f-1)) / 2.
  6. आम्ही हॅश टेबलला मागे टाकू आणि हॅश टेबलमधील प्रत्येक एंट्रीच्या समकक्ष डोमिनोजींची संख्या सांगून समकक्ष डॉमिनोजींची एकूण संख्या मोजू.

अंमलबजावणी

समतुल्य डोमिनोज जोडींसाठी सी ++ कोड

#include <bits/stdc++.h> 
using namespace std; 
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        unordered_map<int, int> count;
        int res = 0;
        for (auto& d : dominoes) {
           count[min(d[0], d[1]) * 10 + max(d[0], d[1])]++;
        }
         for (auto const& pair: count)
         {
          int v= pair.second; 
          res += v * (v - 1) / 2;
         }

        return res;
    }

int main() 
{ 
    vector<vector<int>> dominoes
    {
        {1,2},
        {2,1},
        {3,4},
        {5,6}
    };
int ans=numEquivDominoPairs(dominoes); 
 cout<<ans<<endl;
 return 0;
}
1

समतुल्य डोमिनोज जोडींसाठी जावा कोड

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
    public static int numEquivDominoPairs(int[][] dominoes) {
        Map<Integer, Integer> count = new HashMap<>();
        int res = 0;
        for (int[] d : dominoes) {
            int k = Math.min(d[0], d[1]) * 10 + Math.max(d[0], d[1]);
            count.put(k, count.getOrDefault(k, 0) + 1);
        }
        for (int v : count.values()) {
            res += v * (v - 1) / 2;
        }
        return res;
    }
  public static void main(String[] args) {
        int[][] dominoes=
    {
        {1,2},
        {2,1},
        {3,4},
        {5,6}
    };
        int ans=numEquivDominoPairs(dominoes); 
        System.out.println(ans);
  }
}
1

समतुल्य डोमिनोज पेअर्स लिटकोड सोल्यूशनच्या संख्येचे जटिलता विश्लेषण

वेळ गुंतागुंत

वरील कोडची वेळ जटिलता आहे O (n) कारण आम्ही फक्त एकदाच डोमिनोज अ‍ॅरेचा शोध घेत आहोत. येथे n डोमिनोज अ‍ॅरेची लांबी आहे.

जागेची जटिलता

वरील कोडची स्पेस कॉम्प्लेक्सिटी आहे O (n) कारण आपण हॅश टेबल बनवत आहोत.

संदर्भ