حداقل تعداد عناصر را حذف کنید به طوری که هیچ عنصر مشترکی در هر دو آرایه وجود نداشته باشد


سطح دشواری ساده
اغلب در خوشحال MetLife Oxigen Wallet ServiceNow Spotify
صف مخلوط

با توجه به دو آرایه A و B به ترتیب متشکل از n و m عناصر. حداقل تعداد عناصر را حذف کنید تا هیچ عنصر مشترکی در هر دو وجود نداشته باشد صف و تعداد عناصر حذف شده را چاپ کنید.

مثال

ورودی:

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

B [] = {1 ، 1}

خروجی:

حداقل عناصر برای حذف از هر آرایه 3 است.

ایده اصلی

فرض کنیم یک عنصر num داریم که در هر دو آرایه مشترک است. Num چندین بار در آرایه A و Y چندین بار در آرایه B ظاهر می شود. بنابراین برای اینکه نقطه تلاقی دو آرایه خالی باشد ، سه گزینه داریم:

  1. تمام وقایع num را از آرایه A حذف کنید.
  2. تمام وقایع num را از آرایه B حذف کنید.
  3. اکنون ، همه وقایع num را از A و B حذف کنید.

از آنجا که باید حداقل تعداد عملیات را انجام دهیم ، از میان این سه گزینه ، 1 را انتخاب می کنیمst اگر X کمتر از Y باشد ، یا 2 را انتخاب کنیدnd اگر 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 را به ans اضافه خواهیم کرد.

برای عنصر 2 ، حداقل (3 ، 1) = 1 را به ans اضافه خواهیم کرد.

اکنون ، برای عنصر 3 ، حداقل (1 ، 0) = 0 را به ans اضافه خواهیم کرد.

برای عنصر 4 ، حداقل (1 ، 2) = 1 را به ans اضافه خواهیم کرد.

برای عنصر 20 ، حداقل (0 ، 1) = 0 را به ans اضافه خواهیم کرد.

ans نهایی = 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).

منابع