सरणी में सभी तत्वों को समान बनाने के लिए न्यूनतम संचालन


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना ब्लैकरॉक गढ़ डायरेक्टी फ्लिपकार्ट वास्तव में Yandex
ऐरे hashing

समस्या "सरणी में सभी तत्वों को समान बनाने के लिए न्यूनतम संचालन" बताता है कि आपको ए सरणी कुछ के साथ पूर्णांकों इस में। आपको न्यूनतम संचालन का पता लगाना होगा जो किसी सरणी को समान बनाने के लिए किया जा सकता है।

उदाहरण

सरणी में सभी तत्वों को समान बनाने के लिए न्यूनतम संचालन

[ 1,3,2,4,1]
3

व्याख्या

या तो 3 घटाया जा सकता है या 3 जोड़ एक समान सरणी बनाने के लिए किया जा सकता है।

[5,3,2,4,1]
4

व्याख्या

या तो 4 घटाया जा सकता है या 4 जोड़ एक समान सरणी बनाने के लिए किया जा सकता है।

सभी तत्वों को समान बनाने के लिए न्यूनतम संचालन खोजने के लिए एल्गोरिदम

  1. डिक्लेयर ए नक्शा.
  2. जबकि i <n, लूप जारी है
    1. मानचित्र में प्रत्येक तत्व की सरणी तत्व और आवृत्तियों को संग्रहीत करें।
  3. सेट "अधिकतम" 0 लिए.
  4. लूप की जाँच करें यदि "अधिकतम" एक नक्शे में कुंजी के मूल्य से कम है
    1. अगर हालत संतोषजनक है, तो सेट करें "अधिकतम" कुंजी के मूल्य के लिए।
  5. वापसी (n - "maxCount")।

व्याख्या

हम एक है पूर्णांक सरणी इनपुट के रूप में। हमारा कार्य न्यूनतम संचालन का पता लगाना है जो किसी सरणी को समान बनाने के लिए किया जा सकता है। हम इसमें एक मानचित्र का उपयोग करने जा रहे हैं। मानचित्र का उपयोग करते हुए, हम तत्वों को उनकी आवृत्तियों के साथ आसानी से संग्रहीत कर सकते हैं, क्योंकि संचालन का पता लगाने के लिए आवृत्तियों की महत्वपूर्ण भूमिका होती है।

हम अधिकतम आवृत्ति के साथ तत्व का पता लगाने जा रहे हैं और हम सरणी की लंबाई और अधिकतम आवृत्ति गणना के बीच के अंतर को वापस करते हैं क्योंकि हमारे पास पहले से ही एक सरणी में तत्व है जो दोहराया जाता है इसलिए सभी तत्वों को समान बनाने के लिए कम संचालन होता है जैसा कि यह किसी विशेष को बदलने के बजाय है और यही कारण है कि (सरणी की लंबाई- अधिकतम आवृत्ति) यह यहां काम करता है।

आइए हम यहां एक उदाहरण पर विचार करें:

उदाहरण

गिरफ्तारी: {1, 5, 2, 1, 3, 2, 1};

पहले सबसे तत्व से शुरू होकर, हम पूरे ऐरे को पार करते हैं और प्रत्येक तत्व की आवृत्ति को गिनते हैं और इसे मैप में स्टोर करते हैं।

i = 0,

arr [i] = 1

गिनतीफ्रेक = [१: १]

i = 1

arr [i] = 5

countFreq = [1: 1,5: 1]

i = 2

arr [i] = 2

countFreq = [1: 1,5: 1,2: 1]

i = 3

arr [i] = 1

countFreq = [1: 2,5: 1,2: 1] => यहां हम दो बार तत्व "1" को खोजेंगे जिससे 1 की आवृत्ति गिनती बढ़ेगी।

i = 4

arr [i] = 3

countFreq=[1:2,5:1,2:1,3:1]

i = 5

arr [i] = 2

countFreq = [1: 2,5: 1,2: 2: 3: 1] => यहां हम दो बार तत्व "2" को पाएंगे, इसलिए 2 की आवृत्ति गिनती में वृद्धि होगी।

i = 6

arr [i] = 1

countFreq = [1: 3,5: 1,2: 2: 3: 1] => यहां हमें "1" तत्व मिलेगा, जिससे 1 की आवृत्ति गिनती बढ़ जाएगी।

अब इनिशियलाइज़ करें "अधिकतम" 0. से अधिक है और प्रत्येक आवृत्ति के लिए जाँच करें "अधिकतम", यदि यह अधिक पाया जाता है, तो उस आवृत्ति के मान को स्टोर करें "अधिकतम"

अंत में, हमारे पास सबसे बड़ी आवृत्ति होगी "अधिकतम".

हम n- "अधिकतम" => 7-3 = 4, यही है कि हमें सरणी को समान बनाने के लिए न्यूनतम 4 ऑपरेशन करने चाहिए।

कोड

सरणी में सभी तत्वों को समान बनाने के लिए न्यूनतम ऑपरेशन खोजने के लिए C ++

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

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

  int maxCount = 0;
  for (auto i : countFreq)
    if (maxCount < i.second)
      maxCount = i.second;

  return (n - maxCount);
}
int main()
{
  int arr[] = {1, 5, 2, 1, 3, 2, 1};
  int n = sizeof(arr) / sizeof(arr[0]);
  cout << getMinimumOperation(arr, n);
  return 0;
}
4

जावा कोड सरणी में सभी तत्वों को समान बनाने के लिए न्यूनतम संचालन खोजने के लिए

import java.util.*;
class minimumOperations
{
    public static int getMinimumOperations(int arr[], int n)
    {
        HashMap<Integer, Integer> countFreq = new HashMap<Integer, Integer>();

        for (int i=0; i<n; i++)
        {
            if(countFreq.containsKey(arr[i]))
            {
                countFreq.put(arr[i], countFreq.get(arr[i])+1);
            }
            else
            {
                countFreq.put(arr[i], 1);
            }
        }
        int maxCount = 0;

        Set<Integer> s = countFreq.keySet();

        for (int i : s)
            if (maxCount < countFreq.get(i))
                maxCount = countFreq.get(i);


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

जटिलता विश्लेषण

समय जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है।

अंतरिक्ष जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है।