Опишите на языке программирования алгоритм подсчета максимального количества подряд идущих элементов

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

Учитывая массив размера n, найдите все элементы в массиве, которые появляются более n/k раз. Есть два элемента, которые появляются более двух раз, 2 и 3. Простой метод состоит в том. Чтобы выбрать все элементы один за другим. Для каждого выбранного элемента подсчитайте его вхождения, пересекая массив. Если count становится больше, чем n/k. А затем выведите элемент. Временная сложность этого метода будет O(n2).
Лучшим решением является использование сортировки. Сначала отсортируйте все элементы с помощью алгоритма 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; 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[]. Наша задача-попытаться уложить одно и то же число в один и тот же столбец (количество во временном массиве увеличивается).

Рассмотрим k = 4, n = 9 Заданный массив: 3 1 2 2 2 1 4 3 3 i = 0 3 _ _ temp[] имеет один элемент, 3 со счетом 1 i = 1 3 1 _ temp[] имеет два элемента, 3 и 1 с отсчетами 1 и 1 соответственно i = 2 3 1 2 temp[] имеет три элемента, 3, 1 и 2 с отсчетами 1, 1 и 1 соответственно. i = 3 - - 2 3 1 2 temp[] имеет три элемента: 3, 1 и 2 со счетчиками 1, 1 и 2 соответственно. i = 4 - - 2 - - 2 3 1 2 temp[] имеет три элемента: 3, 1 и 2 с отсчетами 1, 1 и 3 соответственно. i = 5 - - 2 - 1 2 3 1 2 temp[] имеет три элемента: 3, 1 и 2 с отсчетами 1, 2 и 3 соответственно.

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

i = 6 - - 2 - 1 2 temp[] имеет два элемента, 1 и 2 со счетами 1 и 2 соответственно. i = 7 - 2 3 1 2 temp[] имеет три элемента, 3, 1 и 2 со счетами 1, 1 и 2 соответственно. i = 8 3 - 2 3 1 2 temp[] имеет три элемента, 3, 1 и 2 с графами 2, 1 и 2 соответственно.

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

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

C++

#include

using namespace std;

  

struct eleCount {

    int e;

    int c;

};

  

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

{

    

    

    if (k

        return;

  

    

       

       

       

       

    struct eleCount temp[k - 1];

    for (int i = 0; i

        temp[i].c = 0;

  

    

      

    for (int i = 0; i

    {

        int j;

  

        

           

           

         

        for (j = 0; j

        {

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

            {

                temp[j].c += 1;

                break;

            }

        }

  

        

        if (j == k - 1) {

            int l;

  

            

              

              

              

            for (l = 0; l

            {

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

                {

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

                    temp[l].c = 1;

                    break;

                }

            }

  

            

               

               

            if (l == k - 1)

                for (l = 0; l

                    temp[l].c -= 1;

        }

    }

  

    

     

    for (int i = 0; i

    {

        

        int ac = 0;

        for (int j = 0; j

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

                ac++;

  

        

       

        if (ac > n / k)

            cout "Number:"

                 " Count:"

    }

}

  

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;

}

Ява

Python3

С#

Выход

Первый тест Количество:4 Количество:3 Второе испытание Количество:2 Отсчета:2 Третье испытание Количество:2 Отсчета:2 Четвертый тест Число:2 Количество:2 Количество:3 Количество:2

Временная сложность: O(nk)
Вспомогательное пространство: O(k)
Обычно задаваемые вариации этой задачи заключаются в том. Чтобы найти все элементы. Которые появляются n/3 раза или n/4 раза в O(n) временной сложности и O(1) дополнительном пространстве.

Другой Подход:

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

Ниже приводится реализация вышеприведенной идеи:

C++

#include

using namespace std;

  

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

{

    int x = n / k;

      

      

    unordered_mapint, int> freq;

  

    for(int i = 0; i

    {

        freq[arr[i]]++;

    }

    

      

    for(auto i : freq)

    {

          

        

        

        if (i.second > x)

        {

              

            

            

            cout

        }

    }

}

  

int main()

{

    int arr[] = { 1, 1, 2, 2, 3, 5, 

                  4, 2, 2, 3, 1, 1, 1 };

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

    int k = 4;

      

    morethanNbyK(arr, n, k);

  

    return 0;

}

  

Ява

Python3

С#

Язык JavaScript

Выход

1 2

Метод № 2:Использование встроенных функций Python:

  • Подсчитайте частоты каждого элемента с помощью функции Counter ().
  • Пройдитесь по частотному массиву и выведите все элементы. Которые встречаются более n/k раз.

Ниже приводится реализация:

Python3

from collections import Counter

  

def printElements(arr, n, k):

  

    

    x = n//k

  

    

    

    mp = Counter(arr)

      

    

    

    

    for it in mp:

        if mp[it] > x:

            print(it)

  

  

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

n = len(arr)

k = 4

  

printElements(arr, n, k)

  

Выход:

1 2

Временная сложность: O(N)

Вспомогательное пространство: O(N)