ਐਰੇ ਸਮਾਨ ਦੇ ਸਾਰੇ ਐਲੀਮੈਂਟਸ ਬਣਾਉਣ ਲਈ ਘੱਟੋ ਘੱਟ ਓਪਰੇਸ਼ਨਜ਼


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਅਡੋਬ ਤੱਥ
ਅਰੇ ਹੈਸ਼

ਮੰਨ ਲਓ ਕਿ ਸਾਡੇ ਕੋਲ ਇੱਕ ਇੰਪੁੱਟ ਹੈ ਐਰੇ ਨਾਲ "ਐਕਸ" ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ. ਅਸੀਂ ਇੱਕ ਸਮੱਸਿਆ ਦਿੱਤੀ ਹੈ ਕਿ ਸਾਨੂੰ ਮਿਟਾਉਣ ਦੇ ਕਾਰਜਾਂ ਨੂੰ ਲੱਭਣਾ ਹੈ, ਜੋ ਕਿ ਘੱਟੋ ਘੱਟ ਹੋਣਾ ਚਾਹੀਦਾ ਹੈ ਜਿਸ ਨੂੰ ਬਰਾਬਰ ਐਰੇ ਬਣਾਉਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ, ਐਰੇ ਵਿੱਚ ਬਰਾਬਰ ਤੱਤ ਸ਼ਾਮਲ ਹੋਣਗੇ.

ਉਦਾਹਰਨ

ਇੰਪੁੱਟ:

[1, 1, 4, 6, 2, 1]

ਆਉਟਪੁੱਟ:

3

ਸਪਸ਼ਟੀਕਰਨ:

(4, 6, 2) 3 ਤੱਤ ਹਟਾਉਣ ਤੋਂ ਬਾਅਦ ਐਰੇ ਬਰਾਬਰ ਬਣ ਜਾਂਦੇ ਹਨ, [1, 1, 1]

ਇੰਪੁੱਟ:

[1, 5, 4, 16, 32, 9]

ਆਉਟਪੁੱਟ:

5

ਸਪਸ਼ਟੀਕਰਨ:

ਇਸ ਨੂੰ ਬਰਾਬਰ ਐਰੇ ਬਣਾਉਣ ਲਈ ਅਸੀਂ 5 ਤੱਤ ਵਿਚੋਂ ਕਿਸੇ ਨੂੰ ਵੀ ਹਟਾ ਸਕਦੇ ਹਾਂ.

ਐਲਗੋਰਿਥਮ

  1. ਨਕਸ਼ੇ ਵਿੱਚ ਐਰੇ ਦੇ ਸਾਰੇ ਤੱਤਾਂ ਦੀ ਬਾਰੰਬਾਰਤਾ ਨੂੰ ਸਟੋਰ ਕਰੋ.
  2. ਸੈੱਟ ਕਰੋ “ਮੈਕਸ_ਫ੍ਰੇਕ” ਨੂੰ INT_MIN.
  3. ਨਕਸ਼ੇ 'ਤੇ ਨਜ਼ਰ ਮਾਰੋ ਅਤੇ ਵੇਖੋ ਕਿ ਕਿਹੜੇ ਤੱਤ ਦੀ ਜ਼ਿਆਦਾ ਬਾਰੰਬਾਰਤਾ ਹੈ.
    • ਸੈੱਟ ਕਰੋ “ਮੈਕਸ_ਫ੍ਰੇਕ” ਨੂੰ ਅਧਿਕਤਮ (ਅਧਿਕਤਮ_ਫ੍ਰੇਕ, ਮੁੱਲ) ਸਭ ਫ੍ਰੀਕੁਐਂਸੀ ਦੇ ਵਿੱਚ ਵੱਧ ਤੋਂ ਵੱਧ ਮੁੱਲ ਲੱਭਣ ਲਈ.
  4. ਐਰੇ ਅਕਾਰ ਦੇ ਵਿਚਕਾਰ ਅੰਤਰ ਵਾਪਸ ਕਰੋ “ਐਨ” ਅਤੇ ਮੈਕਸ_ਫ੍ਰੇਕ (ਐਨ - ਮੈਕਸ_ਫ੍ਰੇਕ).

ਕਥਾ

ਅਸੀਂ ਇੱਕ ਸਮੱਸਿਆ ਦਿੱਤੀ ਹੈ ਜਿਸ ਵਿੱਚ ਸਾਨੂੰ ਇਹ ਪਤਾ ਕਰਨਾ ਹੈ ਕਿ ਘੱਟੋ ਘੱਟ ਕਿੰਨੀ ਹੈ ਮਿਟਾਉਣਾ ਓਪਰੇਸ਼ਨਾਂ ਲਈ ਐਰੇ ਨੂੰ ਬਰਾਬਰ ਕਰਨ ਲਈ ਲੋੜੀਂਦਾ ਹੁੰਦਾ ਹੈ (ਸਮਾਨ ਤੱਤਾਂ ਦੇ). ਇਸਦੇ ਲਈ, ਅਸੀਂ ਸਟੋਰ ਕਰਨ ਲਈ ਇੱਕ ਨਕਸ਼ੇ ਦੀ ਵਰਤੋਂ ਕਰਨ ਜਾ ਰਹੇ ਹਾਂ ਆਵਿਰਤੀ ਐਰੇ ਵਿੱਚ ਮੌਜੂਦ ਹਰੇਕ ਨੰਬਰ ਦੀ.

ਇਸ ਤਰ੍ਹਾਂ ਕਰਨ ਨਾਲ, ਸਾਡੇ ਕੋਲ ਉਹ ਬਾਰੰਬਾਰਤਾ ਹੋਵੇਗੀ ਜੋ ਸਾਰੀਆਂ ਬਾਰੰਬਾਰਤਾਵਾਂ ਵਿਚੋਂ ਸਭ ਤੋਂ ਵੱਡੀ ਹੈ. ਨਕਸ਼ੇ ਨੂੰ ਦੁਹਰਾਉਣ ਨਾਲ, ਅਸੀਂ ਵੱਧ ਤੋਂ ਵੱਧ ਵਿਧੀ ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਵੱਧ ਤੋਂ ਵੱਧ ਬਾਰੰਬਾਰਤਾ ਪ੍ਰਾਪਤ ਕਰ ਸਕਦੇ ਹਾਂ. ਦੁਹਰਾਉਣ ਤੋਂ ਬਾਅਦ ਫੋਲਡਰ ਨੂੰ ਸਾਡੇ ਕੋਲ ਅਧਿਕਤਮ ਬਾਰੰਬਾਰਤਾ ਹੋਵੇਗੀ ਅਤੇ ਸਾਨੂੰ ਐਰੇ_ਸਾਈਜ਼ - ਵੱਧ ਬਾਰੰਬਾਰਤਾ ਵਾਪਸ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ, ਇਸਦਾ ਮਤਲਬ ਹੈ ਕਿ ਅਸੀਂ ਘੱਟ ਫ੍ਰੀਕੁਐਂਸੀ ਦੀ ਕੁੱਲ ਸੰਖਿਆ ਵਾਪਸ ਕਰ ਰਹੇ ਹਾਂ ਜੋ ਐਰੇ ਨੂੰ ਬਰਾਬਰ ਬਣਾਉਣ ਲਈ ਹਟਾਏ ਜਾ ਸਕਦੇ ਹਨ.

ਆਓ ਇੱਕ ਉਦਾਹਰਣ ਤੇ ਵਿਚਾਰ ਕਰੀਏ:

ਅਰੁ: {10, 3, 4, 4, 2, 4};

  • i = 0, ਇਹ ਆਰਰ [i] 10 ਅਤੇ ਸਟੋਰ ਫ੍ਰੀਕ (10, 1) ਦੇ ਰੂਪ ਵਿੱਚ ਲੈਂਦਾ ਹੈ.
  • i = 1, ਇਹ ਆਰਰ [i] 3 ਅਤੇ ਸਟੋਰ ਫ੍ਰੀਕ (3, 1) ਦੇ ਰੂਪ ਵਿੱਚ ਲੈਂਦਾ ਹੈ.
  • ਆਈ = 2 ਲਈ, ਇਹ ਆਰਰ [i] 4 ਅਤੇ ਸਟੋਰ ਫ੍ਰੀਕ (4, 1) ਵਜੋਂ ਲੈਂਦਾ ਹੈ.
  • i = 3, ਇਹ ਏਰ [i] ਨੂੰ 4 ਦੇ ਰੂਪ ਵਿੱਚ ਲੈਂਦਾ ਹੈ, ਕਿਉਂਕਿ ਨਕਸ਼ੇ ਵਿੱਚ 4 ਪਹਿਲਾਂ ਹੀ ਜਗ੍ਹਾ ਰੱਖਦਾ ਹੈ, ਇਹ ਸਿਰਫ ਇੱਕ ਮਹੱਤਵਪੂਰਨ ਜਗ੍ਹਾ 4 ਅਤੇ ਸਟੋਰ ਫ੍ਰੀਕ (4, 2) ਦੇ ਮਹੱਤਵਪੂਰਨ ਸਥਾਨ ਤੇ ਜੋੜਦਾ ਹੈ.
  • i = 4, ਇਹ ਏਰਰ [i] ਨੂੰ 2 ਦੇ ਰੂਪ ਵਿੱਚ ਲੈਂਦਾ ਹੈ ਅਤੇ ਫ੍ਰੀਕ (2, 1) ਸਟੋਰ ਕਰਦਾ ਹੈ.
  • ਆਈ = for ਲਈ, ਇਹ ਏਰਰ [i] as ਦੇ ਰੂਪ ਵਿਚ ਲੈਂਦਾ ਹੈ, ਕਿਉਂਕਿ ਨਕਸ਼ੇ ਵਿਚ already ਦੀ ਪਹਿਲਾਂ ਹੀ ਜਗ੍ਹਾ ਹੈ ਇਹ it ਅਤੇ ਸਟੋਰ ਫ੍ਰੀਕ (,,)) ਦੇ ਕੁੰਜੀ ਜਗ੍ਹਾ 'ਤੇ ਇਕ ਹੋਰ ਗਿਣਤੀ ਜੋੜਦਾ ਹੈ.

ਇਸ ਸਭ ਵਿਚੋਂ ਸਿਰਫ ਨੰਬਰ '4' ਦੀ ਅਧਿਕਤਮ ਬਾਰੰਬਾਰਤਾ ਹੈ ਜੋ 3 ਹੈ ਅਤੇ ਨਕਸ਼ੇ ਤੋਂ ਵੱਧ ਤੋਂ ਵੱਧ ਬਾਰੰਬਾਰਤਾ ਲੱਭਣ ਅਤੇ ਲੱਭਣ ਤੋਂ ਬਾਅਦ, ਅਸੀਂ ਮੁੱਲ ਵਾਪਸ ਕਰਨ ਜਾ ਰਹੇ ਹਾਂ (n - max_freq) 3. ਇਹ ਸਾਡੀ ਆਉਟਪੁੱਟ ਹੈ.

ਲਾਗੂ

ਐਰੇ ਸਮਾਨ ਦੇ ਸਾਰੇ ਐਲੀਮੈਂਟਸ ਬਣਾਉਣ ਲਈ ਘੱਟੋ ਘੱਟ ਮਿਟਾਉਣ ਵਾਲੀਆਂ ਕਾਰਵਾਈਆਂ ਲਈ ਸੀ ++ ਪ੍ਰੋਗਰਾਮ

#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;
}
3

ਐਰੇ ਸੇਮ ਦੇ ਸਾਰੇ ਐਲੀਮੈਂਟਸ ਬਣਾਉਣ ਲਈ ਮਿਨੀਮਮ ਮਿਟਾਓ ਓਪਰੇਸ਼ਨਸ ਲਈ ਜਾਵਾ ਪ੍ਰੋਗਰਾਮ

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));
    }
}
3

ਐਰੇ ਸਮਾਨ ਦੇ ਸਾਰੇ ਤੱਤਾਂ ਨੂੰ ਬਣਾਉਣ ਲਈ ਘੱਟੋ ਘੱਟ ਮਿਟਾਉਣ ਵਾਲੀਆਂ ਕਾਰਵਾਈਆਂ ਲਈ ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ) ਜਿੱਥੇ “ਐਨ” ਐਰੇ ਵਿਚਲੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਹੈ

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਨ) ਜਿੱਥੇ “ਐਨ” ਐਰੇ ਵਿਚਲੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਹੈ