Группировка множественных вхождений элементов массива, упорядоченных по первому вхождению


Сложный уровень Легко
Часто спрашивают в Акколит саман Амазонка Деливери Фуркиты
массив Hash

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

Пример

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

[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. Удалите этот arr [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 в массиве, он не будет присутствовать в hashmap и не будет печататься.

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 в массиве, он не будет присутствовать в hashmap и не будет печататься.

Теперь у нас будет результат 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

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

Сложность времени

О (п) в котором «Н» это количество элементов в массиве.

Космическая сложность

О (п) в котором «Н» это количество элементов в массиве.

Справка