두 배열 모두에 공통 요소가 없도록 최소 요소 수 제거

난이도 쉽게
자주 묻는 질문 얼레이션 메트 라이프 Oxigen 지갑 ServiceNow 스포티 파이
배열 해시조회수 34

각각 n과 m 요소로 구성된 두 개의 배열 A와 B가 주어집니다. 둘 다에 공통 요소가 없도록 최소 요소 수 제거 정렬 제거 된 요소의 개수를 인쇄합니다.

입력:

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

B [] = {1, 1}

출력:

각 배열에서 제거 할 최소 요소는 3 개입니다.

주요 아이디어

두 배열에서 공통적 인 요소 num이 있다고 가정 해 봅시다. Num은 배열 A에 X 번, Y는 배열 B에 나타납니다. 따라서 두 배열의 교차를 null로 만들려면 세 가지 옵션이 있습니다.

  1. 배열 A에서 num 항목을 모두 제거합니다.
  2. 배열 B에서 num 항목을 모두 제거합니다.
  3. 이제 A와 B 모두에서 num의 모든 항목을 제거하십시오.

최소한의 작업을 수행해야하므로이 세 가지 옵션 중에서 1 개를 선택합니다.st X가 Y보다 작은 경우 옵션 또는 2nd Y가 X보다 작은 경우 옵션.

배열에있는 각 요소의 발생 횟수를 계산하기 위해 해시 테이블을 사용합니다.

최소 요소 수 제거 알고리즘

  1. 답변을 저장할 변수 ans를 초기화하십시오.
  2. 배열을 반복하고 두 배열에 대한 해시 테이블의 모든 요소 발생을 저장합니다.
  3. 배열의 각 요소 num에 대해 X가 A에서 num의 발생 횟수이고 Y가 B에서 num의 발생 횟수 인 경우 ans에 minimum (X, Y)을 추가합니다.
  4. 반환 ans.

예를 들어 이해

우리가 가지고 있다고합시다

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

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

이제 위의 배열에 대한 해시 테이블을 만듭니다.

두 배열에 공통 요소가 없도록 최소 요소 수 제거

요소 0의 경우 ans에 minimum (1, 0) = 0을 추가합니다.

요소 2의 경우 ans에 minimum (3, 1) = 1을 추가합니다.

이제 요소 3의 경우 ans에 minimum (1, 0) = 0을 추가합니다.

요소 4의 경우 ans에 minimum (1, 2) = 1을 추가합니다.

요소 20의 경우 ans에 minimum (0, 1) = 0을 추가합니다.

최종 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).

참조

Translate »