Број еквивалентних Домино парова решење са кодом


Ниво тешкоће Лако
Често питани у амазонка
Ред

Изјава о проблему

У проблему „Број еквивалентних домино парова“, дата нам је листа домина где се свака домина састоји од две вредности попут домина [и] = [а, б]. Две домине, домине [и] = [а, б] и домине [ј] = [ц, д] су еквивалентне ако (а == ц и б == д) или (а == д и ц == д) .

Број еквивалентних Домино парова решење са кодом

Наш задатак је да откријемо укупан број пара (и, ј) где је и! = Ј и домине [и] еквивалент доминама [ј]. Дате вредности а и б леже у опсегу [1,9].

Пример

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

objašnjenje: У овом примеру домине [0] су еквивалентне доминама [1] јер задовољавају услов (а == д и ц == д). Како је ово једини пар који задовољава еквивалентне домино критеријуме, тако је и одговор један.

Приступ за број еквивалентних Домино парова Решење са кодом са кодовима

Овај проблем можемо решити избором домине, а затим провером свих осталих преосталих домина да ли су еквивалентне одабраном домину или не. урадићемо ово за све домине, а затим поделити укупан број еквивалентних домина са 2 даће одговор. Али временска сложеност за овај приступ била би О (н * н). Овај проблем можемо решити за О (н) време следећи следеће кораке:

  1. Претворићемо два броја (а, б) у један број, то ће олакшати проверу еквиваленције.
  2. Ова хеш функција претвориће два броја у један број ц = мин (а, б) * 10 + мак (а, б).
  3. Сада ћемо створити хеш таблицу за бројање учесталости сваког броја.
  4. Прећи ћемо низ домина и сачуваћемо фреквенцију ц у хеш табели.
  5. Након израчунавања учесталости ц вредности можемо израчунати број еквивалентних домина. Претпоставимо да број к има ф фреквенцију у хеш табели, тада ће број еквивалентних парова за вредност к бити фЦ2 који је (ф * (ф-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

Анализа сложености броја еквивалентних Домино парова решења са кодом

Временска сложеност

Временска сложеност горњег кода је Он) јер само једном прелазимо низом домина. Овде је н дужина низа домина.

Свемирска сложеност

Сложеност простора горњег кода је Он) јер креирамо хеш табелу.

Референце