Кількість рівноцінних пар доміно з розчином Леткод


Рівень складності Легко
Часто запитують у Амазонка
масив

Постановка проблеми

У задачі «Кількість еквівалентних пар доміно» ми отримуємо список доміно, де кожне доміно складається з двох значень, таких як доміно [i] = [a, b]. Два доміно, доміно [i] = [a, b] та доміно [j] = [c, d] еквівалентні, якщо (a == c і b == d) або (a == d і c == d) .

Кількість рівноцінних пар доміно з розчином Леткод

Наше завдання - з’ясувати загальну кількість пар (i, j), де i! = J і доміно [i] еквівалент до доміно [j]. Задані значення a і b лежать в межах [1,9].

Приклад

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

Пояснення: У цьому прикладі доміно [0] еквівалентно доміно [1], оскільки воно відповідає умові (a == d і c == d). Оскільки це єдина пара, яка відповідає еквівалентним критеріям доміно, то відповідь одна.

Підхід до кількості рівноцінних розчинів пар доміно Leetcode

Ми можемо вирішити цю проблему, вибравши доміно, а потім перевіривши всі інші доміно, що залишилися, еквівалентні вони вибраному доміно чи ні. ми зробимо це для всіх доміно, а потім розділимо загальну кількість еквівалентних доміно на 2 і дамо відповідь. Але часова складність для цього підходу буде O (n * n). Ми можемо вирішити цю проблему за час O (n), виконавши такі дії:

  1. Ми перетворимо два числа (a, b) в одне число, це полегшить перевірку еквівалентності.
  2. Ця хеш-функція перетворить два числа в одне число c = min (a, b) * 10 + max (a, b).
  3. Тепер ми створимо хеш-таблицю для підрахунку частоти кожного числа.
  4. Ми перейдемо масив доміно і збережемо частоту c у хеш-таблиці.
  5. Після розрахунку частоти значень c ми можемо розрахувати кількість еквівалентних доміно. Припустимо, число 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

Код Java для кількості еквівалентних пар доміно

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

Аналіз складності кількості рівноцінних розчинів Лет-коду пар Доміно

Часова складність

Часова складність вищевказаного коду становить О (п) тому що ми об'їжджаємо масив доміно лише один раз. Тут n - довжина масиву доміно.

Космічна складність

Складність простору наведеного коду становить О (п) тому що ми створюємо хеш-таблицю.

посилання