Рубрики

Учитывая массив размера n и числа k, найдите все элементы, которые появляются более чем в n / k раз

По массиву размером n найдите все элементы в массиве, которые появляются более чем в n / k раз. Например, если входные массивы равны {3, 1, 2, 2, 1, 2, 3, 3} и k равен 4, то выходной сигнал должен быть [2, 3]. Обратите внимание, что размер массива равен 8 (или n = 8), поэтому нам нужно найти все элементы, которые появляются более 2 (или 8/4) раз. Есть два элемента, которые появляются более двух раз, 2 и 3.

Простой способ — выбрать все элементы по одному. Для каждого выбранного элемента подсчитайте его вхождения, пройдя массив, если число становится больше, чем n / k, затем напечатайте элемент. Сложность времени этого метода будет O (n 2 ).

Лучшее решение — использовать сортировку . Сначала отсортируйте все элементы, используя алгоритм O (nLogn). Как только массив отсортирован, мы можем найти все необходимые элементы в линейном сканировании массива. Таким образом, общая временная сложность этого метода составляет O (nLogn) + O (n), что равно O (nLogn).

Ниже приводится интересное решение O (nk):
Мы можем решить вышеупомянутую проблему за O (nk) время, используя O (k-1) дополнительное пространство. Обратите внимание, что в выводе никогда не может быть больше k-1 элементов (почему?). Этот алгоритм состоит в основном из трех этапов.

1) Создайте временный массив размера (k-1) для хранения элементов и их количества (выходные элементы будут среди этих элементов k-1). Ниже приведена структура элементов временного массива.

struct eleCount {
    int element;
    int count;
}; 
struct eleCount temp[]; 

Этот шаг занимает O (K) времени.

2) Пройдите через входной массив и обновите temp [] (добавьте / удалите элемент или увеличьте / уменьшите счетчик) для каждого пройденного элемента. Массив temp [] хранит потенциальных (k-1) кандидатов на каждом шаге. Этот шаг занимает O (NK) времени.

3) Итерация по конечным (k-1) потенциальным кандидатам (хранится в temp []). или каждый элемент, проверьте, действительно ли он имеет больше n / k. Этот шаг занимает O (NK) времени.

Основным шагом является шаг 2, как сохранить (k-1) потенциальных кандидатов в каждой точке? Шаги, использованные в шаге 2, похожи на известную игру: тетрис . Мы рассматриваем каждое число как кусок в тетрисе, который падает в нашем временном массиве temp []. Наша задача состоит в том, чтобы попытаться сохранить одинаковое число в одном и том же столбце (счетчик во временном массиве увеличивается).

Consider k = 4, n = 9 
Given array: 3 1 2 2 2 1 4 3 3 

i = 0
         3 _ _
temp[] has one element, 3 with count 1

i = 1
         3 1 _
temp[] has two elements, 3 and 1 with 
counts 1 and 1 respectively

i = 2
         3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 1 and 1 respectively.

i = 3
         - - 2 
         3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 1 and 2 respectively.

i = 4
         - - 2 
         - - 2 
         3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 1 and 3 respectively.

i = 5
         - - 2 
         - 1 2 
         3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 2 and 3 respectively. 

Теперь возникает вопрос, что делать, когда temp [] заполнен и мы видим новый элемент — мы удаляем нижнюю строку из стеков элементов, т. Е. Уменьшаем количество каждого элемента на 1 в temp []. Мы игнорируем текущий элемент.

i = 6
         - - 2 
         - 1 2 
temp[] has two elements, 1 and 2 with
counts as 1 and 2 respectively.

i = 7
           - 2 
         3 1 2 
temp[] has three elements, 3, 1 and 2 with
counts as 1, 1 and 2 respectively.

i = 8          
         3 - 2
         3 1 2 
temp[] has three elements, 3, 1 and 2 with
counts as 2, 1 and 2 respectively.

Наконец, у нас есть не более k-1 чисел в temp []. Элементы в temp являются {3, 1, 2}. Обратите внимание, что счетчики в temp [] теперь бесполезны, они нужны были только на шаге 2. Теперь нам нужно проверить, больше ли фактическое количество элементов в temp [] больше n / k (9/4) или нет. Элементы 3 и 2 имеют число больше 9/4. Итак, мы печатаем 3 и 2.

Обратите внимание, что алгоритм не пропускает ни одного выходного элемента. Там может быть две возможности, много вхождений вместе или распределены по массиву. Если вхождения встречаются вместе, то количество будет высоким и не станет 0. Если вхождения распространены, то элемент снова появится в temp []. Следующее — реализация C ++ вышеупомянутого алгоритма.

// Программа на C ++ для печати элементов с числом больше n / k
#include<iostream>

using namespace std;

  
// Структура для хранения элемента и его текущего количества

struct eleCount

{

    int e;  // Элемент

    int c;  // считать

};

  
// Печатает элементы с более чем n / k вхождениями в arr [] of
// размер n. Если таких элементов нет, то ничего не печатается.

void moreThanNdK(int arr[], int n, int k)

{

    // k должно быть больше 1, чтобы получить вывод

    if (k < 2)

       return;

  

    / * Шаг 1: Создать временный массив (содержит элемент

       и считать) размера к-1. Инициализировать количество всех

       элементы как 0 * /

    struct eleCount temp[k-1];

    for (int i=0; i<k-1; i++)

        temp[i].c = 0;

  

    / * Шаг 2: Обработка всех элементов входного массива * /

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

    {

        int j;

  

        / * Если arr [i] уже присутствует в

           массив счетчиков элементов, затем увеличить его счетчик * /

        for (j=0; j<k-1; j++)

        {

            if (temp[j].e == arr[i])

            {

                 temp[j].c += 1;

                 break;

            }

        }

  

        / * Если arr [i] отсутствует в temp [] * /

        if (j == k-1)

        {

            int l;

              

            / * Если в temp [] есть доступная позиция, то поместите

              arr [i] в первой доступной позиции и установить счет как 1 * /

            for (l=0; l<k-1; l++)

            {

                if (temp[l].c == 0)

                {

                    temp[l].e = arr[i];

                    temp[l].c = 1;

                    break;

                }

            }

  

            / * Если все позиции в temp [] заполнены, то

               уменьшить количество каждого элемента на 1 * /

            if (l == k-1)

                for (l=0; l<k; l++)

                    temp[l].c -= 1;

        }

    }

  

    / * Шаг 3: Проверьте фактическое количество потенциальных кандидатов в temp [] * /

    for (int i=0; i<k-1; i++)

    {

        // Рассчитать фактическое количество элементов

        int ac = 0;  // фактический счет

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

            if (arr[j] == temp[i].e)

                ac++;

  

        // Если фактическое количество больше чем n / k, то напечатайте это

        if (ac > n/k)

           cout << "Number:" << temp[i].e

                << " Count:" << ac << endl;

    }

}

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

int main()

{

    cout << "First Test\n";

    int arr1[] = {4, 5, 6, 7, 8, 4, 4};

    int size = sizeof(arr1)/sizeof(arr1[0]);

    int k = 3;

    moreThanNdK(arr1, size, k);

  

    cout << "\nSecond Test\n";

    int arr2[] = {4, 2, 2, 7};

    size = sizeof(arr2)/sizeof(arr2[0]);

    k = 3;

    moreThanNdK(arr2, size, k);

  

    cout << "\nThird Test\n";

    int arr3[] = {2, 7, 2};

    size = sizeof(arr3)/sizeof(arr3[0]);

    k = 2;

    moreThanNdK(arr3, size, k);

  

    cout << "\nFourth Test\n";

    int arr4[] = {2, 3, 3, 2};

    size = sizeof(arr4)/sizeof(arr4[0]);

    k = 3;

    moreThanNdK(arr4, size, k);

  

    return 0;

}

Выход:

First Test
Number:4 Count:3

Second Test
Number:2 Count:2

Third Test
Number:2 Count:2

Fourth Test
Number:2 Count:2
Number:3 Count:2

Сложность времени: O (нк)
Вспомогательное пространство: O (k)

Обычно задаются варианты этой проблемы: найдите все элементы, которые появляются n / 3 раза или n / 4 раза в O (n) сложности времени и O (1) лишнем пространстве.

Хеширование также может быть эффективным решением. С хорошей хэш-функцией мы можем решить вышеупомянутую проблему в среднем за O (n) раз. Дополнительное пространство, необходимое для хеширования, будет выше, чем O (k). Кроме того, хеширование не может быть использовано для решения вышеуказанных изменений с O (1) дополнительным пространством.

Упражнение:
Вышеупомянутая проблема может быть решена за время O (nLogk) с помощью более подходящих структур данных, чем массив для вспомогательного хранения k-1 элементов. Предложите подход O (nLogk).

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

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

Учитывая массив размера n и числа k, найдите все элементы, которые появляются более чем в n / k раз

0.00 (0%) 0 votes