배열의 모든 요소를 동일하게 만들기위한 최소 삭제 작업-

Twitter Facebook 링크드 인 버퍼 레딧 텀블러

다음과 같은 입력이 있다고 가정합니다. 정렬 + "X" 요소 수. 우리는 동일한 배열을 만드는 데 필요한 최소값이어야하는 삭제 작업을 찾아야한다는 문제가 있습니다. 즉, 배열은 동일한 요소로 구성됩니다.

차례

예

입력:

[1, 1, 4, 6, 2

출력:

설명 :

(4, 6, 2) 3 개의 요소를 제거한 후 배열은 동일하게됩니다. 즉, [1, 1, 1]

입력:

[1, 5, 4, 16, 32

출력:

설명 :

5 개 요소 중 하나를 제거하여 동일한 배열로 만들 수 있습니다.

암호알고리즘

배열의 모든 요소의 빈도를지도에 저장합니다.
세트 "최대_주파수" 에 INT_MIN.
지도를 반복하고 최대 빈도가있는 요소를 확인합니다.
- 세트 "최대_주파수" 에 최대 (최대 _ 주파수, 값) 모든 주파수 중에서 최대 값을 찾습니다.
배열 크기의 차이를 반환 "엔" 및 max_freq (n – max_freq).

설명

우리는 얼마나 많은 최소값을 찾아야하는 문제를주었습니다. 삭제 (유사한 요소의) 배열을 동일하게 만들려면 연산이 필요합니다. 이를 위해지도를 사용하여 주파수 배열에있는 각 숫자의.

이렇게하면 모든 주파수 중에서 가장 큰 주파수를 갖게됩니다. 지도를 반복하면 max 메소드를 사용하여 최대 주파수를 얻을 수 있습니다. 반복 후 지도 우리는 최대 주파수를 가질 것이고 array_size를 반환해야합니다 – 최대 주파수, 그것은 배열을 동일하게 만들기 위해 제거 할 수있는 더 적은 주파수의 총 수를 반환한다는 것을 의미합니다.

예를 들어 보겠습니다.

arr : {10, 3, 4, 4, 2, 4};

i = 0, arr [i]를 10으로하고 freq (10, 1)을 저장합니다.
i = 1, arr [i]를 3으로하고 freq (3, 1)을 저장합니다.
i = 2 인 경우 arr [i]를 4로하고 freq (4, 1)을 저장합니다.
i = 3이면 arr [i]를 4로 취합니다. 4는 이미지도에 위치가 있기 때문에 4의 주요 위치에 계수를 하나 더 추가하고 freq (4, 2)를 저장합니다.
i = 4, arr [i]를 2로하고 freq (2, 1)을 저장합니다.
i = 5의 경우 arr [i]를 4로 취합니다. 4는 이미지도에 위치가 있기 때문에 4의 주요 위치에 계수를 하나 더 추가하고 freq (4, 3)을 저장합니다.

이 모든 숫자 중 '4'는 최대 주파수가 3이고지도에서 최대 주파수를 3으로 찾은 후 값을 반환합니다 (n – max_freq). 3. 그것이 우리의 결과입니다.

실시

배열의 모든 요소를 동일하게 만들기위한 최소 삭제 작업을위한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

int minDelete(int arr[], int n)
{
    unordered_map<int, int> freq;
    for (int i = 0; i < n; i++)
        freq[arr[i]]++;

    int max_freq = INT_MIN;

    for (auto itr = freq.begin(); itr != freq.end(); itr++)
        max_freq = max(max_freq, itr->second);

    return n - max_freq;
}
int main()
{
    int arr[] = { 10, 3, 4, 4, 2, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << minDelete(arr, n);
    return 0;
}

배열의 모든 요소를 동일하게 만들기위한 최소 삭제 작업을위한 Java 프로그램

import java.util.HashMap;
class minimumDeletionOperation
{
    public static int noOfMinimumDeletions(int arr[], int n)
    {
        HashMap<Integer,Integer> freq=new HashMap<Integer,Integer>();
        for(int i=0; i<arr.length; i++)
        {
            if(freq.containsKey(arr[i]))
                freq.put(arr[i], freq.get(arr[i]) + 1);
            else
                freq.put(arr[i], 1);
        }

        int max_freq=Integer.MIN_VALUE;

        for (int i:freq.keySet())
            max_freq = Math.max(max_freq, freq.get(i));

        return n - max_freq;
    }
    public static void main(String args[])
    {
        int arr[] = { 10, 3, 4, 4, 2, 4 };
        int n = arr.length;
        System.out.println(noOfMinimumDeletions(arr, n));
    }
}

배열의 모든 요소를 동일하게 만들기위한 최소 삭제 작업에 대한 복잡성 분석

시간 복잡성

O (n) 여기서 "엔" 배열의 요소 수입니다.

공간 복잡성