ആദ്യ സംഭവമനുസരിച്ച് ക്രമീകരിച്ച അറേ ഘടകങ്ങളുടെ ഗ്രൂപ്പ് ഒന്നിലധികം സംഭവങ്ങൾ


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

നിങ്ങൾ‌ക്ക് ഒരു ചോദ്യം നൽ‌കി, അതിൽ‌ നിങ്ങൾ‌ തരംതിരിക്കാത്തവ നൽകി ശ്രേണി ഒന്നിലധികം സംഖ്യകളോടെ. ആദ്യ സംഭവമനുസരിച്ച് ക്രമീകരിച്ച അറേ ഘടകങ്ങളുടെ ഒന്നിലധികം സംഭവങ്ങളെ ഗ്രൂപ്പുചെയ്യുക എന്നതാണ് ചുമതല. അതേസമയം, ഓർഡർ നമ്പർ വരുന്നതിന് തുല്യമായിരിക്കണം.

ഉദാഹരണം

ഇൻപുട്ട്:

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

ഔട്ട്പുട്ട്:

[2 2 3 3 3 4 4 1]

ഇൻപുട്ട്:

[5,4,1,5,4,1,5,6]

ഔട്ട്പുട്ട്:

[5 5 5 4 4 1 1 6]

അൽഗോരിതം

  1. പ്രഖ്യാപിക്കുക ഹാഷ്‌മാപ്പ്.
  2. അറേയിലൂടെ സഞ്ചരിച്ച് എല്ലാ ഘടകങ്ങളും അതിന്റെ ആവൃത്തിയും ഹാഷ്‌മാപ്പിൽ ഇടുക.
  3. അറേയിലൂടെ സഞ്ചരിക്കുമ്പോൾ ഓരോ ഘടകത്തിന്റെയും ആവൃത്തി നേടുക.
    1. ആ ഫ്രീക്വൻസി സമയം വരെ ആ കീ പ്രിന്റുചെയ്യുക.
    2. ആ അറ നീക്കംചെയ്യുക [i] (കീ).

അറേ ഘടകങ്ങളുടെ ഗ്രൂപ്പ് ഒന്നിലധികം സംഭവങ്ങൾക്കുള്ള വിശദീകരണം

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

ആദ്യം, ഞങ്ങൾ ഒരു ഹാഷ് മാപ്പ് “മൈമാപ്പ്” എന്ന് പ്രഖ്യാപിക്കും. തുടർന്ന് ഞങ്ങൾ മുഴുവൻ ശ്രേണിയും സഞ്ചരിച്ച് എണ്ണുകയും സംഭരിക്കുകയും ചെയ്യുന്നു ആവൃത്തി ഓരോ ഘടകത്തിന്റെയും.

നമുക്ക് ഒരു ഉദാഹരണം പരിഗണിച്ച് അത് മനസ്സിലാക്കാം.

ഉദാഹരണം

arr = [5, 4, 1, 5, 4, 1, 5, 6]

i = 0, arr [i] = 5

myMap = {5: 1}

i = 1, arr [i] = 4

myMap = {4: 1,5: 1}

i = 2, arr [i] = 1

myMap = {1: 1,4: 1,5: 1}

i = 3, arr [i] = 5

myMap = {1: 1,4: 1,5: 2}

i = 4, arr [i] = 4

myMap = {1: 1,4: 2,5: 2}

i = 5, arr [i] = 1

myMap = {1: 2,4: 2,5: 2}

i = 6, arr [i] = 5

myMap = {1: 2,4: 2,5: 3}

i = 6, arr [i] = 6

myMap={1:2,4:2,5:3,6:1}

ഇപ്പോൾ നമുക്ക് അതിൽ ഒരു മൈമാപ്പും മൂല്യങ്ങളും ഉണ്ടാകും.

ഒരു അറേയിലെ ഓർഡർ ചെയ്ത ഘടകത്തിനൊപ്പം ഒരു അറേയിലൂടെ വീണ്ടും സഞ്ചരിച്ചതിന് ശേഷം ഞങ്ങൾക്ക് ആവൃത്തി ലഭിക്കും. ഓരോ അറേ ഘടകത്തെയും അതിന്റെ ആവൃത്തി ഉപയോഗിച്ച് എടുത്ത് ആ ആവൃത്തി സമയം വരെ ഒരു ലൂപ്പ് ഉണ്ടാക്കുക, ആവൃത്തി സമയം ആ അറേ കീ നീക്കംചെയ്യുന്നതുവരെ എല്ലാ അറേ ഘടകങ്ങളും അച്ചടിച്ചതിന് ശേഷം അത് കൂടുതൽ സഞ്ചാരത്തിൽ വീണ്ടും അച്ചടിക്കില്ല.

വര [i] = 5 ആവൃത്തി = 3

5 പ്രിന്റുചെയ്യും, 3 തവണ, തുടർന്ന് ഞങ്ങൾ ആ കീ മൈമാപ്പിൽ നീക്കംചെയ്യും, അതിനാൽ ഒരു അറേയിൽ 5 വായിക്കുമ്പോഴെല്ലാം അത് ഹാഷ്‌മാപ്പിൽ ദൃശ്യമാകില്ല, അച്ചടിക്കുകയുമില്ല.

വര [i] = 4 ആവൃത്തി = 2

4 പ്രിന്റുചെയ്യും, 2 തവണ, കീ മാപ്പിൽ നീക്കംചെയ്യും, അതിനാൽ ഞങ്ങൾ ഒരു അറേയിൽ 4 വായിക്കുമ്പോഴെല്ലാം അത് ഹാഷ്‌മാപ്പിൽ ദൃശ്യമാകില്ല, അച്ചടിക്കുകയുമില്ല.

വര [i] = 1 ആവൃത്തി = 2

1 അച്ചടിക്കും, 2 തവണ, തുടർന്ന് ഞങ്ങൾ ആ കീ മൈമാപ്പിൽ നീക്കംചെയ്യും, അതിനാൽ ഒരു അറേയിൽ 5 വായിക്കുമ്പോഴെല്ലാം അത് ഹാഷ്‌മാപ്പിൽ ഉണ്ടാകില്ല, അച്ചടിക്കുകയുമില്ല.

ഇപ്പോൾ 5 ശ്രേണിയിൽ വരുന്നു, പക്ഷേ അത് ഹാഷ്‌മാപ്പിൽ ദൃശ്യമാകില്ല, അത് സംഭവിക്കുകയും ഹാഷ്‌മാപ്പിൽ നിലവിലുള്ള ഘടകം കണ്ടെത്തുന്നതുവരെ ഒന്നും ചെയ്യാതിരിക്കുകയും ചെയ്യുക.

വര [i] = 6 ആവൃത്തി = 1

6 അച്ചടിക്കും, 1 തവണ, കീ മൈമാപ്പിൽ നീക്കംചെയ്യും, അതിനാൽ നമ്മൾ അറേയിൽ 4 വായിക്കുമ്പോഴെല്ലാം അത് ഹാഷ്‌മാപ്പിൽ ദൃശ്യമാകില്ല, അച്ചടിക്കുകയുമില്ല.

5 ട്ട്‌പുട്ട് ഇപ്പോൾ 5 5 4 4 1 1 6 XNUMX ആയി ലഭിക്കും.

നടപ്പിലാക്കൽ

ആദ്യ സംഭവമനുസരിച്ച് ക്രമീകരിച്ച അറേ ഘടകങ്ങളുടെ ഗ്രൂപ്പ് ഒന്നിലധികം സംഭവങ്ങൾക്കായുള്ള സി ++ പ്രോഗ്രാം

#include<iostream>
#include<unordered_map>

using namespace std;
void arrangeInOrder(int arr[], int n)
{
    unordered_map<int, int> myMap;

    for (int i=0; i<n; i++)
    {
        myMap[arr[i]]++;
    }
    for (int i=0; i<n; i++)
    {
        int count = myMap[arr[i]];
        for (int j=0; j<count; j++)
            cout<<arr[i]<< " ";

        myMap.erase(arr[i]);
    }
}
int main()
{
    int arr[] = {10, 5, 3, 10, 10, 4, 1, 3};
    int n=sizeof(arr)/sizeof(arr[0]);
    arrangeInOrder(arr,n);
    return 0;
}
10 10 10 5 3 3 4 1

ജാവ പ്രോഗ്രാം

import java.util.HashMap;

class multipleOccurences
{
    public static void arrangeInOrder(int arr[])
    {
        HashMap<Integer, Integer> myMap= new HashMap<Integer, Integer>();

        for (int i=0; i<arr.length; i++)
        {
            Integer current = myMap.get(arr[i]);
            if (current == null)
                current = 0;

            myMap.put(arr[i], current + 1);
        }
        for (int i=0; i<arr.length; i++)
        {
            Integer count = myMap.get(arr[i]);
            if (count != null)
            {
                for (int j=0; j<count; j++)
                {
                    System.out.print(arr[i] + " ");
                }
                myMap.remove(arr[i]);
            }
        }
    }
    public static void main (String[] args)
    {
        int arr[] = {10, 5, 3, 10, 10, 4, 1, 3};
        arrangeInOrder(arr);
    }
}
10 10 10 5 3 3 4 1

അറേ ഘടകങ്ങളുടെ ഗ്രൂപ്പ് ഒന്നിലധികം സംഭവങ്ങൾക്കായുള്ള സങ്കീർണ്ണത വിശകലനം

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

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

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

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

അവലംബം