Выдаліце ​​мінімальную колькасць элементаў, каб у абодвух масівах не існавала агульнага элемента


Узровень складанасці Лёгка
Часта пытаюцца ў Алацыя MetLife Кіслародны кашалёк ServiceNow Spotify
масіў гашыш

Дадзены два масівы A і B, якія складаюцца з n і m элементаў адпаведна. Выдаліце ​​мінімальную колькасць элементаў, каб у абодвух не існавала агульнага элемента масіў і раздрукуйце колькасць элементаў, якія былі выдалены.

Прыклад

Уваход:

A [] = {1, 2, 1, 1}

B [] = {1, 1}

Вынахад:

Мінімум элементаў для выдалення з кожнага масіва - 3.

Галоўная ідэя

Скажам, у нас ёсць элемент num, які распаўсюджаны ў абодвух масівах. Num з'яўляецца X колькасць разоў у масіве A і Y колькасць разоў у масіве B. Такім чынам, каб зрабіць перасячэнне двух масіваў нулявым, у нас ёсць тры варыянты:

  1. Выдаліць усе выпадкі num з масіва A.
  2. Выдаліць усе выпадкі num з масіва B.
  3. Цяпер выдаліце ​​ўсе выпадкі num з A і B.

Паколькі нам трэба зрабіць мінімальную колькасць аперацый, з гэтых трох варыянтаў мы абярэм 1st варыянт, калі X менш, чым Y, альбо 2nd варыянт, калі Y менш за X.

Для падліку ўваходжання кожнага элемента ў масівы мы будзем выкарыстоўваць хэш-табліцу.

Алгарытм выдалення мінімальнай колькасці элементаў

  1. Ініцыялізуйце зменную ans, якая будзе захоўваць адказ.
  2. Перабірайце масівы і захоўвайце ўваходжанне кожнага элемента ў хэш-табліцу для абодвух масіваў.
  3. Для кожнага элемента num ў масівах, калі X - колькасць выпадкаў num ў A, а Y - колькасць выпадкаў num ў B, дадайце мінімум (X, Y) да ans.
  4. Вяртанне анс.

Зразумейце на прыкладзе

Скажам, маем

A [] = {2, 3, 2, 2, 0, 4}

B [] = {4, 4, 2, 20}

Цяпер мы робім хэш-табліцу для вышэйзгаданых масіваў.

Выдаліце ​​мінімальную колькасць элементаў, каб у абодвух масівах не існавала агульнага элемента

Для элемента 0 мы дадамо мінімум (1, 0) = 0 да анса.

Для элемента 2 мы дадамо мінімум (3, 1) = 1 да анса.

Цяпер для элемента 3 мы дадамо мінімум (1, 0) = 0 да анса.

Для элемента 4 мы дадамо мінімум (1, 2) = 1 да анса.

Для элемента 20 мы дадамо мінімум (0, 1) = 0 да анса.

Канчатковы анс = 2.

Праграма C ++ для выдалення мінімальнай колькасці элементаў

#include <bits/stdc++.h>
using namespace std;
int MinElementsToRemove(vector<int> &A, vector<int> &B)
{
    unordered_map<int, int> count_A, count_B;
    for (auto ele : A)
    {
        count_A[ele]++;
    }
    for (auto ele : B)
    {
        count_B[ele]++;
    }
    int ans = 0;
    for (auto ele : count_A)
    {
        if (count_B.count(ele.first) == 1)
        {
            ans += min(count_B[ele.first], count_A[ele.first]);
        }
    }
    return ans;
}
int main()
{
    vector<int> A = {2, 3, 2, 2, 0, 4};
    vector<int> B = {4, 4, 2, 20};
    cout << "Minimum number of elements to remove from each array such that no common element exist in both array: " << MinElementsToRemove(A, B) << endl;
    return 0;
}
Minimum number of elements to remove from each array such that no common element exist between both array: 2

Праграма JAVA для выдалення мінімальнай колькасці элементаў

import java.util.*;
public class Main
{
    public static int MinElementsToRemove(int[] A, int[] B)
    {
        Map<Integer, Integer> count_A 
            = new HashMap<Integer, Integer>(); 
        Map<Integer, Integer> count_B
            = new HashMap<Integer, Integer>(); 
        for (int i=0; i<A.length;i++)
        {
            Integer j =count_A.get(A[i]); 
            count_A.put(A[i], (j == null) ? 1 : j + 1); 
        }
        for (int i=0; i<B.length;i++)
        {
            Integer j =count_B.get(B[i]); 
            count_B.put(B[i], (j == null) ? 1 : j + 1); 
        }
        int ans = 0;
        for (Map.Entry<Integer, Integer> entry : count_A.entrySet()){
            if (count_B.get(entry.getKey())!=null)
            {
                ans += Math.min(count_B.get(entry.getKey()), count_A.get(entry.getKey()));
            }
        }
        return ans;
    }
  public static void main(String[] args) {
      int[] A = {2, 3, 2, 2, 0, 4};
        int[] B = {4, 4, 2, 20};
    System.out.println("Minimum number of elements to remove from each array such that no common element exist in both array: "+MinElementsToRemove(A, B));
  }
}


Minimum number of elements to remove from each array such that no common element exist between both array: 2

Аналіз складанасці для Выдаліце ​​мінімальную колькасць элементаў

Часовая складанасць

Як мы перабіраем абодва масівы адзін раз, так і агульная складанасць часу складае O (N + M).

Касмічная складанасць

Мы выкарыстоўвалі дзве хэш-табліцы для захоўвання частаты элементаў для абодвух масіваў, таму складанасць прасторы складаная O (N + M).

Спасылкі