Групувати кілька випадків елементів масиву, упорядкованих за першим випадком


Рівень складності Легко
Часто запитують у Accolite саман Амазонка Делівері Фуркіти
масив Мішанина

Вам задають питання, в якому ви даєте невідсортований масив з кількома входженнями чисел. Завдання полягає в групуванні всіх множинних випадків елементів масиву, упорядкованих за першим входженням. Тим часом замовлення має бути таким самим, як і номер.

Приклад

Вхідний сигнал:

[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. Декларуйте HashMap.
  2. Обведіть масив і помістіть усі елементи та його частоту в HashMap.
  3. Під час обходу масиву отримуємо частоту кожного елемента.
    1. Роздрукуйте цю клавішу до цієї частоти.
    2. Видаліть цей аргумент [i] (ключ).

Пояснення щодо групового багаторазового виникнення елементів масиву

Для цього ми використаємо хешування. Хешування надає функцію зберігання елементів як пари ключ-значення. У цьому питанні ми будемо використовувати ключ як елемент масиву, а значення як частоту кожного елемента. Ми просто вставляємо елемент, якщо його немає в хеш-таблиці. в іншому випадку збільшити кількість (ключ-значення) елемента.

По-перше, ми оголосимо HashMap сказати “myMap”. Потім ми обходимо весь масив і підраховуємо та зберігаємо частота кожного елемента.

Давайте розглянемо приклад і зрозуміємо його.

Приклад

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 і значення в ній.

Ми отримаємо частоту після повторного обходу масиву з упорядкованим елементом у масиві. Беручи кожен елемент масиву з його частотою, і робіть цикл до цього періоду частоти і після друку всіх елементів масиву, поки частота разів не виймає цей ключ масиву, щоб він не друкував знову при подальшому обміні.

Arr [i] = 5 частота = 3

5 буде надруковано 3 рази, тоді ми видалимо цей ключ у myMap, тому всякий раз, коли ми читаємо 5 у масиві, він не буде присутній у хеш-капі та не друкується.

Arr [i] = 4 частота = 2

4 буде надруковано 2 рази, ключ буде видалено в myMap, тому всякий раз, коли ми читаємо 4 у масиві, він не буде присутній у HashMap і не друкується.

Arr [i] = 1 частота = 2

1 буде надруковано 2 рази, тоді ми видалимо цей ключ у myMap, тому кожного разу, коли ми читаємо 5 у масиві, і він не буде присутній у HashMap і не друкується.

Тепер 5 поставляється в масиві, але він не буде присутній у HashMap, і те саме відбувається і нічого не робить, поки не буде знайдений елемент, який присутній у HashMap.

Arr [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

Програма Java

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" - кількість елементів у масиві.

Посилання