Рубрики

Сортировать элементы по частоте | Набор 2

По массиву целых чисел отсортируйте массив по частоте элементов. Например, если входной массив равен {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12}, измените массив на {3, 3, 3, 3, 2, 2, 2, 12, 12, 4, 5}.

В предыдущем посте мы обсудили все методы сортировки по частоте. В этом посте метод 2 подробно обсуждается, и для него предоставляется реализация на C ++.

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

  • Создайте BST и при создании BST поддерживайте частоту каждого входящего элемента в том же BST. Этот шаг может занять O (nLogn) время, если используется самобалансирующийся BST.
  • Выполните Inorder обход BST и сохраните каждый элемент и количество каждого элемента во вспомогательном массиве. Давайте назовем вспомогательный массив как 'count []'. Обратите внимание, что каждый элемент этого массива является элементом и парой частот. Этот шаг занимает O (N) времени.
  • Сортировка 'count []' по частоте элементов. Этот шаг занимает время O (nLohn), если используется алгоритм сортировки O (nLogn).
  • Пройдите через отсортированный массив count []. Для каждого элемента x выведите его «freq», где «freq» — частота x. Этот шаг занимает O (N) времени.

Общая временная сложность алгоритма может быть минимальной O (nLogn), если мы используем алгоритм сортировки O (nLogn) и используем самобалансировку BST с операцией вставки O (Logn) .

Ниже приведена реализация вышеуказанного алгоритма.

// Реализация вышеуказанного алгоритма в C ++.
#include <iostream>
#include <stdlib.h>

using namespace std;

  
/ * Узел BST имеет указатели на данные, частоту, левый и правый * /

struct BSTNode

{

    struct BSTNode *left;

    int data;

    int freq;

    struct BSTNode *right;

};

  
// Структура для хранения данных и их частота

struct dataFreq

{

    int data;

    int freq;

};

  
/ * Функция для реализации qsort (). Сравните частоты с

   отсортировать массив по убыванию частоты * /

int compare(const void *a, const void *b)

{

    return ( (*(const dataFreq*)b).freq - (*(const dataFreq*)a).freq );

}

  
/ * Вспомогательная функция, которая выделяет новый узел с данными данными,

   частота как 1 и NULL левый и правый указатели. * /

BSTNode* newNode(int data)

{

    struct BSTNode* node = new BSTNode;

    node->data = data;

    node->left = NULL;

    node->right = NULL;

    node->freq = 1;

    return (node);

}

  
// Вспомогательная функция для вставки данного ключа в BST. Если элемент
// уже присутствует, затем увеличивает частоту

BSTNode *insert(BSTNode *root, int data)

{

    if (root == NULL)

        return newNode(data);

    if (data == root->data) // Если уже присутствует

        root->freq += 1;

    else if (data < root->data)

        root->left = insert(root->left, data);

    else

        root->right = insert(root->right, data);

    return root;

}

  
// Функция для копирования элементов и их частот для подсчета [].

void store(BSTNode *root, dataFreq count[], int *index)

{

    // Базовый вариант

    if (root == NULL) return;

  

    // Повторение для левого поддерева

    store(root->left, count, index);

  

    // Сохраняем элемент из корня и индекса приращения

    count[(*index)].freq = root->freq;

    count[(*index)].data = root->data;

    (*index)++;

  

    // Повтор для правого поддерева

    store(root->right, count, index);

}

  
// Основная функция, которая принимает входной массив в качестве аргумента
// и сортирует элементы массива по частоте

void sortByFrequency(int arr[], int n)

{

    // Создать пустой BST и вставить все элементы массива в BST

    struct BSTNode *root = NULL;

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

        root = insert(root, arr[i]);

  

    // Создаем вспомогательный массив count [] для хранения данных и

    // частотные пары. Максимальный размер этого массива будет

    // быть, когда все элементы разные

    dataFreq count[n];

    int index = 0;

    store(root, count, &index);

  

    // Сортировка массива count [] по частоте (или количеству)

    qsort(count, index, sizeof(count[0]), compare);

  

    // Наконец, переходим отсортированный массив count [] и копируем

    // i'th item 'freq' times до исходного массива 'arr []'

    int j = 0;

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

    {

        for (int freq = count[i].freq; freq > 0; freq--)

            arr[j++] = count[i].data;

    }

}

  
// Вспомогательная функция для печати массива размера n

void printArray(int arr[], int n)

{

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

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

    cout << endl;

}

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

int main()

{

    int arr[] = {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12};

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

    sortByFrequency(arr, n);

    printArray(arr, n);

    return 0;

}

Выход :

3 3 3 3 2 2 2 12 12 5 4

Упражнение:
Вышеприведенная реализация не гарантирует оригинальный порядок элементов с одинаковой частотой (например, 4 идет перед 5 на входе, но 4 идет после 5 на выходе). Расширить реализацию, чтобы сохранить первоначальный порядок. Например, если два элемента имеют одинаковую частоту, выведите тот, который был первым во входном массиве.

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

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

Сортировать элементы по частоте | Набор 2

0.00 (0%) 0 votes