Групирајте вишеструке појаве елемената низа поредане по првом појављивању


Ниво тешкоће Лако
Често питани у Аццолите адобе амазонка Делхивери Фоуркитес
Ред Хасх

Добија се питање у коме сте дали неразврстано поредак са вишеструким појављивањем бројева. Задатак је груписање свих вишеструких појављивања елемената низа пореданих по првом појављивању. У међувремену, редослед би требао бити исти као и број који долази.

Пример

Улаз:

[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. Уклоните тај завој [и] (тастер).

Објашњење за групно вишеструко појављивање елемената низа

За то ћемо користити Хасхинг. Хасхинг пружа могућност чувања елемената као пара кључ / вредност. У овом питању ћемо користити кључ као елемент низа и вредност као фреквенцију сваког елемента. Једноставно убацимо елемент ако није присутан у хеш табели. у супротном повећати број (кључ-вредност) елемента.

Прво ћемо прогласити да ХасхМап каже „моја карта“. Затим прелазимо читав низ и рачунамо и складиштимо фреквенција сваког елемента.

Размотримо пример и схватимо га.

Пример

арр = [5, 4, 1, 5, 4, 1, 5, 6]

и = 0, арр [и] = 5

моја карта = {5: 1}

и = 1, арр [и] = 4

моја карта = {4: 1,5: 1}

и = 2, арр [и] = 1

моја карта = {1: 1,4: 1,5: 1}

и = 3, арр [и] = 5

моја карта = {1: 1,4: 1,5: 2}

и = 4, арр [и] = 4

моја карта = {1: 1,4: 2,5: 2}

и = 5, арр [и] = 1

моја карта = {1: 2,4: 2,5: 2}

и = 6, арр [и] = 5

моја карта = {1: 2,4: 2,5: 3}

и = 6, арр [и] = 6

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

Сада ћемо имати миМап и вредности у њему.

Фреквенцију ћемо добити након поновног преласка низа са уређеним елементом у низу. Узимајући сваки елемент низа са његовом фреквенцијом и направите петљу до тог фреквенцијског времена и након исписа свих елемената низа све док учестала времена не уклоните тај кључ низа, тако да се он неће више штампати у даљем преласку.

Арр [и] = 5 фреквенција = 3

5 ће се одштампати 3 пута, а затим ћемо уклонити тај кључ у мојој мапи, тако да кад год читамо 5 у низу неће бити присутан у хасхмап-у и неће се исписати.

Арр [и] = 4 фреквенција = 2

4 ће бити одштампано, 2 пута, кључ ће бити уклоњен у миМап, тако да кад год читамо 4 у низу неће бити присутан у ХасхМап-у и неће се штампати.

Арр [и] = 1 фреквенција = 2

1 ће се одштампати 2 пута, а затим ћемо уклонити тај кључ у миМап, па кад год читамо 5 у низу и он неће бити присутан у ХасхМап-у и неће се штампати.

Сада долази 5 у низу, али неће бити присутан у ХасхМап-у, а исто се догађа и не ради ништа док се не пронађе елемент који је присутан у ХасхМап-у.

Арр [и] = 6 фреквенција = 1

6 ће бити одштампано, 1 пут, кључ ће бити уклоњен у миМап, тако да кад год читамо 4 у низу неће бити присутан у хасхмап-у и неће се исписати.

Сада ћемо имати излаз као 5 5 5 4 4 1 1 6.

Имплементација

Ц ++ програм за групно вишеструко појављивање елемената низа пореданих по првом појављивању

#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

Анализа сложености за групну вишеструку појаву елемената низа

Сложеност времена

Он) где „Н“ је број елемената у низу.

Сложеност простора

Он) где „Н“ је број елемената у низу.

Препорука