Рубрики

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

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

Примеры:

Input: arr[] = {5, 3, 5, 1, 3, 3}
Output:        {5, 5, 3, 3, 3, 1}

Input: arr[] = {4, 6, 9, 2, 3, 4, 9, 6, 10, 4}
Output:        {4, 4, 4, 6, 6, 9, 9, 2, 3, 10}

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

C ++

// Простая программа на C ++ для группировки нескольких экземпляров
// элементы массива
#include<iostream>

using namespace std;

  
// Простой метод для группировки всех вхождений отдельных элементов

void groupElements(int arr[], int n)

{

    // Инициализируем все элементы как не посещенные

    bool *visited = new bool[n];

    for (int i=0; i<n; i++)

        visited[i] = false;

  

    // Обход всех элементов

    for (int i=0; i<n; i++)

    {

        // Проверяем, является ли это первым появлением

        if (!visited[i])

        {

            // Если да, распечатать его и все последующие вхождения

            cout << arr[i] << " ";

            for (int j=i+1; j<n; j++)

            {

                if (arr[i] == arr[j])

                {

                    cout << arr[i] << " ";

                    visited[j] = true;

                }

            }

        }

    }

  

    delete [] visited;  

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    int arr[] = {4, 6, 9, 2, 3, 4, 9, 6, 10, 4};

    int n = sizeof(arr)/sizeof(arr[0]);

    groupElements(arr, n);

    return 0;

}

Джава

// Простая Java-программа для группировки
// множественные вхождения индивидуума
// элементы массива

  

class GFG

{

  

    // Простой метод для группировки всех вхождений

    // отдельных элементов

    static void groupElements(int arr[], int n) 

    {

          

        // Инициализируем все элементы как не посещенные

        boolean visited[] = new boolean[n];

        for (int i = 0; i < n; i++) 

        {

            visited[i] = false;

        }

  

        // Обход всех элементов

        for (int i = 0; i < n; i++) 

        {

              

            // Проверяем, является ли это первым появлением

            if (!visited[i])

            {

                  

                // Если да, распечатай и все

                // последующие вхождения

                System.out.print(arr[i] + " ");

                for (int j = i + 1; j < n; j++) 

                {

                    if (arr[i] == arr[j]) 

                    {

                        System.out.print(arr[i] + " ");

                        visited[j] = true;

                    }

                }

            }

        }

    }

  

    / * Код водителя * /

    public static void main(String[] args)

    {

        int arr[] = {4, 6, 9, 2, 3, 4

                        9, 6, 10, 4};

        int n = arr.length;

        groupElements(arr, n);

    }

  
// Этот код предоставлен Rajput-JI

python3

# Простая программа на Python 3 для
# группировать множественные вхождения
# отдельные элементы массива

  
# Простой способ сгруппировать все
# вхождения отдельных элементов

def groupElements(arr, n):

  

    # Инициализировать все элементы

    # как не посещенные

    visited = [False] * n

    for i in range(0, n):

        visited[i] = False

  

    # Пройти все элементы

    for i in range(0, n):

      

        # Проверьте, если это

        # первое вхождение

        if (visited[i] == False):

          

            # Если да, распечатайте его и

            # все последующие вхождения

            print(arr[i], end = " ")

            for j in range(i + 1, n):

              

                if (arr[i] == arr[j]):

                  

                    print(arr[i], end = " ")

                    visited[j] = True

              
Код водителя

arr = [4, 6, 9, 2, 3

       4, 9, 6, 10, 4]

n = len(arr)

groupElements(arr, n)

  
# Этот код добавлен
# от Smitha

C #

// Простая программа на C # для группировки
// множественные вхождения индивидуума
// элементы массива

using System;

  

class GFG 

  

    // Простой метод для группировки всех вхождений

    // отдельных элементов

    static void groupElements(int []arr, int n) 

    

          

        // Инициализируем все элементы как не посещенные

        bool []visited = new bool[n]; 

        for (int i = 0; i < n; i++) 

        

            visited[i] = false

        

  

        // Обход всех элементов

        for (int i = 0; i < n; i++) 

        

              

            // Проверяем, является ли это первым появлением

            if (!visited[i]) 

            

                  

                // Если да, распечатай и все

                // последующие вхождения

                Console.Write(arr[i] + " "); 

                for (int j = i + 1; j < n; j++) 

                

                    if (arr[i] == arr[j]) 

                    

                        Console.Write(arr[i] + " "); 

                        visited[j] = true

                    

                

            

        

    

  

    / * Код водителя * /

    public static void Main(String[] args) 

    

        int []arr = {4, 6, 9, 2, 3, 4, 

                        9, 6, 10, 4}; 

        int n = arr.Length; 

        groupElements(arr, n); 

    

  
// Этот код предоставлен PrinciRaj1992


Выход:

4 4 4 6 6 9 9 2 3 10

Временная сложность описанного выше способа составляет O (n 2 ).

Метод, основанный на бинарном дереве поиска : временная сложность может быть улучшена до O (nLogn) с использованием самобалансирующегося бинарного дерева поиска, такого как красно-черное дерево или дерево AVL . Ниже приводится полный алгоритм.
1) Создайте пустое дерево двоичного поиска (BST). Каждый узел BST будет содержать элемент массива и его количество.
2) Перейдите во входной массив и выполните следующие действия для каждого элемента.
…… ..a) Если элемент отсутствует в BST, вставьте его с количеством 0.
…… ..b) Если элемент присутствует, то увеличить счетчик в соответствующем узле BST.
3) Снова просмотрите массив и выполните следующие действия для каждого элемента.
…… .. Если элемент присутствует в BST, то выполните следующее
……… .a) Получить его счетчик и распечатать элемент «count» раз.
……… .b) Удалить элемент из BST.

Сложность времени вышеупомянутого решения составляет O (nLogn).

Метод на основе хеширования: мы также можем использовать хеширование. Идея состоит в том, чтобы заменить двоичное дерево поиска хэш-картой в приведенном выше алгоритме.

Ниже приведена реализация решения на основе хеширования.

Джава

/ * Java-программа для группировки нескольких вхождений отдельных элементов массива * /

import java.util.HashMap;

  

class Main

{

    // Метод на основе хеширования для группировки всех вхождений отдельных элементов

    static void orderedGroup(int arr[])

    {

        // Создаем пустой хэш-карту

        HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();

  

        // Обход элементов массива и сохранение количества для каждого элемента

        // в HashMap

        for (int i=0; i<arr.length; i++)

        {

           // Проверяем, есть ли элемент в HashMap

           Integer prevCount = hM.get(arr[i]);

           if (prevCount == null

                prevCount = 0;

             

           // Увеличиваем количество элементов элемента в HashMap

           hM.put(arr[i], prevCount + 1);

        }

  

        // Переходим массив снова

        for (int i=0; i<arr.length; i++)

        

            // Проверяем, является ли это первым появлением

            Integer count =  hM.get(arr[i]);     

            if (count != null)

            {

                // Если да, то выводим элемент count

                for (int j=0; j<count; j++)

                   System.out.print(arr[i] + " ");

                  

                // И удаляем элемент из HashMap.

                hM.remove(arr[i]);

            }

        }

    }

  

    // Метод драйвера для проверки вышеуказанного метода

    public static void main (String[] args)

    {

        int arr[] = {10, 5, 3, 10, 10, 4, 1, 3};

        orderedGroup(arr);

    }

}

python3

# Python3 программа для группировки нескольких
# вхождения отдельных элементов массива

  
# Метод на основе хеширования для группировки
# все вхождения отдельных элементов

def orderedGroup(arr):

      

    # Создает пустой хэш-карту

    hM = {}

  

    # Обход элементов массива и сохранение

    # количество для каждого элемента в HashMap

    for i in range(0, len(arr)):

          

        # Увеличение количества элементов

        # в HashMap

        hM[arr[i]] = hM.get(arr[i], 0) + 1

          

    Снова пересечь массив

    for i in range(0, len(arr)):

          

        # Проверьте, является ли это первым появлением

        count = hM.get(arr[i], None)     

        if count != None:

              

            # Если да, то распечатать

            # элемент "считать" раз

            for j in range(0, count):

                print(arr[i], end = " ")

                  

            # И удалить элемент из HashMap.

            del hM[arr[i]]

  
Код водителя

if __name__ == "__main__":

      

    arr = [10, 5, 3, 10, 10, 4, 1, 3]

    orderedGroup(arr)

      
# Этот код предоставлен Rituraj Jain

C #

// C # программа для группировки нескольких вхождений
// отдельных элементов массива

using System;

using System.Collections.Generic; 

  

class GFG

{

  
// Метод на основе хеширования для группировки
// все вхождения отдельных элементов

static void orderedGroup(int []arr)

{

    // Создаем пустой хэш-карту

    Dictionary<int

               int> hM = new Dictionary<int,

                                        int>();

  

    // Обход элементов массива,

    // и хранить количество для каждого элемента в HashMap

    for (int i = 0; i < arr.Length; i++)

    {

        // Проверяем, есть ли элемент в HashMap

        int prevCount = 0;

        if (hM.ContainsKey(arr[i])) 

                prevCount = hM[arr[i]];

              

        // Увеличиваем количество элементов элемента в HashMap

        if (hM.ContainsKey(arr[i])) 

            hM[arr[i]] = prevCount + 1;

        else

            hM.Add(arr[i], prevCount + 1);

    }

  

    // Переходим массив снова

    for (int i = 0; i < arr.Length; i++)

    

        // Проверяем, является ли это первым появлением

        int count = 0;

        if (hM.ContainsKey(arr[i]))

            count = hM[arr[i]]; 

        if (count != 0)

        {

            // Если да, то выведите

            // элемент 'count' times

            for (int j = 0; j < count; j++)

            Console.Write(arr[i] + " ");

              

            // И удаляем элемент из HashMap.

            hM.Remove(arr[i]);

        }

    }

}

  
// Код драйвера

public static void Main (String[] args)

{

    int []arr = {10, 5, 3, 10, 10, 4, 1, 3};

    orderedGroup(arr);

}
}

  
// Этот код предоставлен Принчи Сингхом


Выход:

10 10 10 5 3 3 4 1 

Сложность по времени вышеупомянутого решения на основе хеширования составляет Θ (n) при условии, что операции вставки, поиска и удаления в HashMap занимают O (1) времени.

Ниже приведена связанная проблема для строк.
Сгруппируйте все вхождения персонажей в соответствии с первым появлением

Эта статья предоставлена Химаншу Гупта . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

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

0.00 (0%) 0 votes