පළමු සිදුවීම අනුව ඇණවුම් කරන ලද අරා මූලද්‍රව්‍ය සමූහයේ බහු සිදුවීම්  


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇසොලයිට් ඇෙබෝ ඇමේසන් දිල්ලි ෆෝකයිට්
අරා හැෂ්

ඔබ විසින් වර්ග කර නොමැති ප්‍රශ්නයක් ලබා දී ඇත අරාව සංඛ්‍යා වල බහු අවස්ථා සමඟ. කර්තව්යය වන්නේ පළමු සිදුවීම අනුව ඇණවුම් කරන ලද අරාව මූලද්රව්යවල බහුවිධ සිදුවීම් කාණ්ඩ කිරීමයි. මේ අතර, ඇණවුම අංකය පැමිණෙන ආකාරයටම විය යුතුය.

උදාහරණයක්  

ආදානය:

[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. එම අර්‍ගය ඉවත් කරන්න (යතුර).

අරා මූලද්‍රව්‍ය සමූහයේ බහු සිදුවීම් සඳහා පැහැදිලි කිරීම  

අපි ඒ සඳහා හැෂිං භාවිතා කරන්නෙමු. හැෂිං විසින් මූල-අගය යුගලයක් ලෙස මූලද්‍රව්‍ය ගබඩා කිරීමේ අංගයක් සපයයි. මෙම ප්‍රශ්නයේදී, අපි යතුර අරාව මූලද්‍රව්‍යයක් ලෙසත් එක් එක් මූලද්‍රව්‍යයේ සංඛ්‍යාතයක් ලෙස අගයක් ලෙසත් භාවිතා කරන්නෙමු. මූලද්රව්යය හැෂ් වගුවේ නොමැති නම් අපි එය ඇතුල් කරමු. නැතිනම් මූලද්‍රව්‍යයේ ගණන (යතුරු අගය) වැඩි කරන්න.

පළමුව, අපි හැෂ්මැප් “මයිමැප්” යැයි ප්‍රකාශ කරමු. ඉන්පසු අපි මුළු අරාව හරහා ගමන් කර ඒවා ගණන් කර ගබඩා කරමු සංඛ්යාත එක් එක් මූලද්රව්යයේ.

අපි උදාහරණයක් සලකා බලා එය තේරුම් ගනිමු.

උදාහරණයක්

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}

දැන් අපට එහි MyMap සහ අගයන් ඇත.

අරාවෙහි ඇණවුම් කළ මූලද්‍රව්‍යය සමඟ නැවත අරාවක් ගමන් කිරීමෙන් පසු අපට සංඛ්‍යාතය ලැබෙනු ඇත. සෑම අරා මූලද්‍රව්‍යයක්ම එහි සංඛ්‍යාතය සමඟ ගෙන එම සංඛ්‍යාත වේලාව තෙක් ලූපයක් සාදන්න. සංඛ්‍යාත වේලාවන් එම අරාව යතුර ඉවත් කරන තෙක් සියලු අරාව මූලද්‍රව්‍ය මුද්‍රණය කිරීමෙන් පසුව එය නැවත ගමන් කිරීමේදී නැවත මුද්‍රණය නොකෙරේ.

ආ [i] = 5 සංඛ්‍යාතය = 3

5 ක් මුද්‍රණය කෙරෙනු ඇත, 3 වතාවක්, පසුව අපි එම යතුර myMap හි ඉවත් කරන්නෙමු, එබැවින් අපි 5 අරාවකින් කියවන සෑම විටම එය හැෂ්මැප් හි නොපවතින අතර මුද්‍රණය නොකෙරේ.

ආ [i] = 4 සංඛ්‍යාතය = 2

4 මුද්‍රණය කෙරෙනු ඇත, 2 වතාවක්, යතුර myMap හි ඉවත් කරනු ලැබේ, එබැවින් අපි අරාවකින් 4 ක් කියවන සෑම විටම එය හැෂ්මැප් හි නොපවතින අතර මුද්‍රණය නොකෙරේ.

ආ [i] = 1 සංඛ්‍යාතය = 2

1 මුද්‍රණය කරනු ලැබේ, 2 වතාවක්, පසුව අපි එම යතුර myMap හි ඉවත් කරන්නෙමු, එබැවින් අපි 5 ක් අරාවකින් කියවන විට එය හැෂ්මැප් හි නොපවතින අතර මුද්‍රණය නොකෙරේ.

දැන් 5 අරාවෙහි එන නමුත් එය හැෂ්මැප් හි නොපවතින අතර එය සිදු වන අතර හැෂ්මැප් හි ඇති මූලද්‍රව්‍යය සොයා ගන්නා තෙක් කිසිවක් නොකරන්න.

ආ [i] = 6 සංඛ්‍යාතය = 1

6 මුද්‍රණය කෙරෙනු ඇත, 1 වතාවක්, යතුර myMap හි ඉවත් කරනු ලැබේ, එබැවින් අපි අරාවෙහි 4 කියවන සෑම විටම එය හැෂ්මැප් හි නොපවතින අතර මුද්‍රණය නොකෙරේ.

අපට දැන් ප්‍රතිදානය 5 5 5 4 4 1 1 6 ලෙස ලැබෙනු ඇත.

ක්රියාත්මක කිරීම  

පළමු සිදුවීම අනුව ඇණවුම් කරන ලද අරා මූලද්‍රව්‍ය සමූහයේ බහු සිදුවීම් සඳහා C ++ වැඩසටහන

#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

අරා මූලද්‍රව්‍ය සමූහයේ බහු සිදුවීම් සඳහා සංකීර්ණ විශ්ලේෂණය  

කාල සංකීර්ණත්වය

සාමාන්ය (n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.

මෙයද බලන්න
සංයෝජන එකතුව ලීට්කෝඩ් විසඳුම

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.

විමර්ශන