Екі массивте де ортақ элемент болмайтындай элементтердің минималды санын алып тастаңыз


Күрделілік дәрежесі оңай
Жиі кіреді Алация MetLife Oxigen Wallet ServiceNow Spotify
Array Hash

N және m элементтерінен тұратын екі А және В жиымдары берілген. Ешқандай жалпы элемент болмайтындай элементтердің минималды санын алып тастаңыз массив және жойылған элементтердің санын басып шығарыңыз.

мысал

Кіру:

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

B [] = {1, 1}

Шығару:

Әр массивтен алып тастайтын минималды элементтер - 3.

Негізгі ой

Екі жиымға да ортақ num элементі бар делік. Num A массивінде X рет, ал B массивінде рет пайда болады. Екі массивтің қиылысуын нөлге айналдыру үшін бізде үш нұсқа бар:

  1. А массивінен num-дің барлық көріністерін алып тастаңыз.
  2. B массивінен num-дің барлық көріністерін алып тастаңыз.
  3. Енді А-да және В-да num-дің барлық көріністерін алып тастаңыз.

Біз операциялардың минималды санын жасауымыз керек болғандықтан, осы үш нұсқаның ішінен біз 1 таңдаймызst егер X Y немесе 2-ден аз болса, параметрnd егер Y X-ден кіші болса.

Массивтердегі әр элементтің пайда болуын санау үшін біз хэш кестесін қолданамыз.

Минималды элементтер санын жою алгоритмі

  1. Жауапты сақтайтын ans айнымалы инициализациясы.
  2. Жиымдарды қайталап, барлық элементтердің пайда болуын екі массив үшін хэш кестесінде сақтаңыз.
  3. Массивтегі әрбір num элементі үшін, егер X - A-да num-дің пайда болу саны болса, Y-де B-дің пайда болу саны болса, онда ans-ке минималды (X, Y) қосыңыз.
  4. Оралу.

Мысалмен түсіну

Айталық, бізде бар

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

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

Енді біз жоғарыдағы массивтерге хэш-кесте жасаймыз.

Екі массивте де ортақ элемент болмауы үшін элементтердің минималды санын алып тастаңыз

0 элементі үшін ans-ке минимум (1, 0) = 0 қосамыз.

2 элементі үшін ans-ке минимум (3, 1) = 1 қосамыз.

Енді, 3-элемент үшін біз ans-ке минимум (1, 0) = 0 қосамыз.

4 элементі үшін ans-ке минимум (1, 2) = 1 қосамыз.

20 элементі үшін ans-ке минимум (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).

Әдебиеттер тізімі