എല്ലാ ഘടകങ്ങളെയും അറേയിൽ തുല്യമാക്കുന്നതിനുള്ള ഏറ്റവും കുറഞ്ഞ പ്രവർത്തനം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ കറുത്ത പാറ കോട്ട ഡയറക്റ്റി ഫ്ലിപ്പ്കാർട്ട് തീർച്ചയായും യാൻഡക്സ്
അറേ ഹാഷിംഗ്

“എല്ലാ ഘടകങ്ങളെയും അറേയിൽ തുല്യമാക്കുന്നതിനുള്ള ഏറ്റവും കുറഞ്ഞ പ്രവർത്തനം” എന്ന പ്രശ്നം നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു ശ്രേണി ചിലരുമായി പൂർണ്ണസംഖ്യകൾ അതിൽ. ഒരു അറേ തുല്യമാക്കുന്നതിന് ചെയ്യാവുന്ന ഏറ്റവും കുറഞ്ഞ പ്രവർത്തനങ്ങൾ നിങ്ങൾ കണ്ടെത്തണം.

ഉദാഹരണം

എല്ലാ ഘടകങ്ങളെയും അറേയിൽ തുല്യമാക്കുന്നതിനുള്ള ഏറ്റവും കുറഞ്ഞ പ്രവർത്തനം

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

വിശദീകരണം

ഒന്നുകിൽ 3 കുറയ്ക്കൽ നടത്താം അല്ലെങ്കിൽ ഒരു തുല്യ അറേ ഉണ്ടാക്കാൻ 3 കൂട്ടിച്ചേർക്കലുകൾ നടത്താം.

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

വിശദീകരണം

ഒന്നുകിൽ 4 കുറയ്ക്കൽ നടത്താം അല്ലെങ്കിൽ ഒരു തുല്യ അറേ ഉണ്ടാക്കാൻ 4 കൂട്ടിച്ചേർക്കലുകൾ നടത്താം.

എല്ലാ ഘടകങ്ങളും തുല്യമാക്കുന്നതിന് മിനിമം പ്രവർത്തനങ്ങൾ കണ്ടെത്താനുള്ള അൽഗോരിതം

  1. ഒരു പ്രഖ്യാപിക്കുക ഭൂപടം.
  2. ഞാൻ <n ആയിരിക്കുമ്പോൾ, ലൂപ്പ് തുടരുന്നു
    1. ഓരോ ഘടകത്തിന്റെയും അറേ ഘടകവും ആവൃത്തിയും മാപ്പിൽ സംഭരിക്കുക.
  3. ഗണം “പരമാവധി എണ്ണം” 0 ലേക്ക്.
  4. ലൂപ്പിനെ പരിശോധിക്കുന്നുണ്ടോയെന്ന് പരിശോധിക്കുക “പരമാവധി എണ്ണം” ഒരു മാപ്പിലെ കീയുടെ മൂല്യത്തേക്കാൾ കുറവാണ്
    1. വ്യവസ്ഥ തൃപ്‌തികരമാണെങ്കിൽ, സജ്ജമാക്കുക “പരമാവധി എണ്ണം” കീയുടെ മൂല്യത്തിലേക്ക്.
  5. മടങ്ങുക (n - “maxCount”).

വിശദീകരണം

ഞങ്ങൾക്ക് ഒരു ഉണ്ട് പൂർണ്ണസംഖ്യ ശ്രേണി ഇൻപുട്ടായി. ഒരു അറേ തുല്യമാക്കുന്നതിന് ചെയ്യാവുന്ന ഏറ്റവും കുറഞ്ഞ പ്രവർത്തനങ്ങൾ കണ്ടെത്തുക എന്നതാണ് ഞങ്ങളുടെ ചുമതല. ഞങ്ങൾ അതിൽ ഒരു മാപ്പ് ഉപയോഗിക്കാൻ പോകുന്നു. ഒരു മാപ്പ് ഉപയോഗിച്ച്, ഘടകങ്ങളെ അവയുടെ ആവൃത്തി ഉപയോഗിച്ച് എളുപ്പത്തിൽ സംഭരിക്കാൻ ഞങ്ങൾക്ക് കഴിയും, കാരണം പ്രവർത്തനങ്ങൾ കണ്ടെത്തുന്നതിന് ആവൃത്തികൾക്ക് ഒരു പ്രധാന പങ്കുണ്ട്.

പരമാവധി ആവൃത്തിയിലുള്ള ഘടകം ഞങ്ങൾ കണ്ടെത്താൻ പോകുന്നു, അറേയുടെ ദൈർഘ്യവും പരമാവധി ഫ്രീക്വൻസി എണ്ണവും തമ്മിലുള്ള വ്യത്യാസം ഞങ്ങൾ നൽകുന്നു, കാരണം ഞങ്ങൾക്ക് ഇതിനകം ഒരു അറേയിൽ ഘടകം ഉള്ളതിനാൽ ആവർത്തിക്കുന്നു, അതിനാൽ എല്ലാ ഘടകങ്ങളും തുല്യമാക്കുന്നതിന് കുറച്ച് പ്രവർത്തനങ്ങൾ ആവശ്യമാണ് ഒരു പ്രത്യേകത മാറ്റുന്നതിനുപകരം അത് ആയതിനാൽ (അറേയുടെ ദൈർഘ്യം- പരമാവധി ആവൃത്തി) ഇത് ഇവിടെ പ്രവർത്തിക്കുന്നു.

നമുക്ക് ഇവിടെ ഒരു ഉദാഹരണം നോക്കാം:

ഉദാഹരണം

arr: {1, 5, 2, 1, 3, 2, 1};

ആദ്യത്തെ ഏറ്റവും മൂലകത്തിൽ നിന്ന് ആരംഭിച്ച്, ഞങ്ങൾ മുഴുവൻ അറേയിലും സഞ്ചരിച്ച് ഓരോ മൂലകത്തിന്റെയും ആവൃത്തി കണക്കാക്കുകയും മാപ്പിൽ സംഭരിക്കുകയും ചെയ്യുന്നു.

i = 0,

arr [i] = 1

countFreq = [1: 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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.