Рубрики

Сортировать элементы по частоте | Комплект 1

Выведите элементы массива с уменьшающейся частотой, если 2 числа имеют одинаковую частоту, а затем напечатайте первое.

Примеры:

Input:  arr[] = {2, 5, 2, 8, 5, 6, 8, 8}
Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6}

Input: arr[] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}
Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}

МЕТОД 1 (Использовать сортировку)

  • Используйте алгоритм сортировки для сортировки элементов O (nlogn)
  • Сканируйте отсортированный массив и создайте двумерный массив элементов и сосчитайте O (n).
  • Сортируйте двумерный массив по количеству O (nlogn) .

Пример:

  Input 2 5 2 8 5 6 8 8

  After sorting we get
  2 2 5 5 6 8 8 8

  Now construct the 2D array as
  2, 2
  5, 2
  6, 1
  8, 3

  Sort by count
  8, 3
  2, 2
  5, 2
  6, 1

Как сохранить порядок элементов, если частота одинакова? :
Приведенный выше подход не гарантирует порядок элементов, если частота одинакова. Чтобы справиться с этим, мы должны использовать индексы на шаге 3, если два числа одинаковы, тогда мы должны сначала обработать (или распечатать) элемент с более низким индексом. На шаге 1 мы должны хранить индексы вместо элементов.

  Input 5  2  2  8  5  6  8  8

  After sorting we get
  Element 2 2 5 5 6 8 8 8
  Index   1 2 0 4 5 3 6 7

  Now construct the 2D array as
  Index, Count
  1,      2
  0,      2
  5,      1
  3,      3

  Sort by count (consider indexes in case of tie)
  3, 3
  0, 2
  1, 2
  5, 1
  
  Print the elements using indexes in the above 2D array.

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

// Сортировка элементов по частоте. Если два элемента имеют одинаковые
// посчитаем, затем поместим элементы, которые появляются первыми
#include <bits/stdc++.h>

using namespace std;

  
// Используется для сортировки

struct ele {

    int count, index, val;

};

  
// Используется для сортировки по значению

bool mycomp(struct ele a, struct ele b)

{

    return (a.val < b.val);

}

  
// Используется для сортировки по частоте. И если частота одинакова,
// тогда по внешнему виду

bool mycomp2(struct ele a, struct ele b)

{

    if (a.count != b.count)

        return (a.count < b.count);

    else

        return a.index > b.index;

}

  

void sortByFrequency(int arr[], int n)

{

    struct ele element[n];

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

  

        // Заполняем индексы

        element[i].index = i; 

        // Инициализация считается как 0

        element[i].count = 0; 

  

        // Заполняем значения в структуре

        // элементы

        element[i].val = arr[i]; 

    }

  

    / * Сортировать элементы структуры по значению,

       мы использовали стабильную сортировку, поэтому относительный порядок поддерживается. * /

    stable_sort(element, element + n, mycomp);

  

    / * инициализировать счетчик первого элемента как 1 * /

    element[0].count = 1;

  

    / * Подсчет вхождений оставшихся элементов * /

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

        if (element[i].val == element[i - 1].val) {

            element[i].count += element[i - 1].count + 1;

  

            / * Установить счетчик предыдущего элемента как -1, мы

               делая это, потому что мы снова будем сортировать на

               основание счета (если число равно, чем на

               основа индекса) *

            element[i - 1].count = -1;

  

            / * Сохранить первый индекс (Запомнить первый индекс

               всегда присутствует в первом дубликате мы

               используется стабильная сортировка. * /

            element[i].index = element[i - 1].index;

        }

  

        / * Else, если предыдущий элемент не равен текущему

          поэтому установите счетчик в 1 * /

        else

            element[i].count = 1;

    }

  

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

       сортировать по количеству и в случае использования индекса связи

       Сортировать.*/

    stable_sort(element, element + n, mycomp2);

    for (int i = n - 1, index = 0; i >= 0; i--)

        if (element[i].count != -1)

            for (int j = 0; j < element[i].count; j++)

                arr[index++] = element[i].val;

}

  
// Драйвер программы

int main()

{

    int arr[] = { 2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8 };

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

  

    sortByFrequency(arr, n);

  

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

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

    return 0;

}

Выход :

8 8 8 2 2 5 5 6 -1 9999999 

Спасибо Gaurav Ahirwar за предоставленную реализацию.

МЕТОД 2 (использовать BST и сортировку)

  • Вставьте элементы в BST один за другим, и если элемент уже присутствует, увеличьте счетчик узла. Узел дерева двоичного поиска (используемый в этом подходе) будет выглядеть следующим образом.

    struct tree {

        int element;

        int first_index / * Для обработки связей в счетчиках * /

            int count;

    } BST;

  • Сохраните первые индексы и соответствующие значения BST в двумерном массиве.
  • Сортируйте двумерный массив по количеству (и используйте индексы в случае связи).

Сложность времени: O (nlogn), если используется самобалансирующееся дерево двоичного поиска . Это реализовано в наборе 2 .

МЕТОД 3 (использовать хеширование и сортировку)
Используя механизм хеширования, мы можем хранить элементы (также первый индекс) и их количество в хэше. Наконец, сортируйте элементы хеша в соответствии с их количеством.

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

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

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

Сортировать элементы по частоте | Комплект 1

0.00 (0%) 0 votes