Рубрики

Найти максимальное число повторений в O (n) времени и O (1) лишних пробелах

Для данного массива размера n массив содержит числа в диапазоне от 0 до k-1, где k — положительное целое число, а k <= n. Найдите максимальное количество повторений в этом массиве. Например, пусть k будет 10, данный массив будет arr [] = {1, 2, 2, 2, 0, 2, 0, 2, 3, 8, 0, 9, 2, 3}, максимальное число повторений будет быть 2. Ожидаемая сложность времени составляет O (n), а допустимое дополнительное пространство равно O (1) . Изменения в массиве разрешены.

Наивный подход состоит в запуске двух циклов, внешний цикл выбирает элемент один за другим, внутренний цикл подсчитывает количество вхождений выбранного элемента. Наконец, верните элемент с максимальным количеством. Временная сложность этого подхода составляет O (n ^ 2) .

Лучшим подходом является создание массива count размера k и инициализация всех элементов count [] как 0. Итерируйте по всем элементам входного массива, и для каждого элемента arr [i] , увеличивайте счет [arr [i]] . Наконец, выполните итерацию по count [] и верните индекс с максимальным значением. Этот подход занимает O (n) времени, но требует O (k) пространства.

Далее следует O (n) время и O (1) дополнительное пространство . Давайте разберем подход на простом примере, где arr [] = {2, 3, 3, 5, 3, 4, 1, 7}, k = 8, n = 8 (количество элементов в arr []).

1) Итерируйте хотя входной массив arr [] , для каждого элемента arr [i] , увеличивайте arr [arr [i]% k] на k ( arr [] становится {2, 11, 11, 29, 11, 12, 1, 15})

2) Найти максимальное значение в модифицированном массиве (максимальное значение — 29). Индекс максимального значения является максимальным повторяющимся элементом (индекс 29 равен 3).

3) Если мы хотим вернуть исходный массив, мы можем еще раз пройти по массиву и выполнить arr [i] = arr [i]% k, где i изменяется от 0 до n-1 .

Как работает вышеуказанный алгоритм? Поскольку мы используем arr [i]% k в качестве индекса и добавляем значение k к индексу arr [i]% k , индекс, равный максимальному повторяющемуся элементу, будет иметь максимальное значение в конце. Обратите внимание, что k добавляется максимальное количество раз по индексу, равному максимальному повторяющемуся элементу, и все элементы массива меньше k.

Следующее — реализация C ++ вышеупомянутого алгоритма.

C ++

// C ++ программа для поиска максимального повторяющегося числа

  
#include<iostream>

using namespace std;

  
// Возвращает максимальный повторяющийся элемент в arr [0..n-1].
// Элементы массива находятся в диапазоне от 0 до k-1

int maxRepeating(int* arr, int n, int k)

{

    // Итерация по входному массиву для каждого элемента

    // arr [i], увеличиваем arr [arr [i]% k] на k

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

        arr[arr[i]%k] += k;

  

    // Находим индекс максимального повторяющегося элемента

    int max = arr[0], result = 0;

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

    {

        if (arr[i] > max)

        {

            max = arr[i];

            result = i;

        }

    }

  

    / * Раскомментируйте этот код, чтобы вернуть исходный массив

       для (int i = 0; i <n; i ++)

          arr [i] = arr [i]% k; * /

  

    // Возвращаем индекс максимального элемента

    return result;

}

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

int main()

{

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

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

    int k = 8;

  

    cout << "The maximum repeating number is " <<

         maxRepeating(arr, n, k) << endl;

  

    return 0;

}

Джава

// Java программа для поиска максимального повторяющегося числа

import java.io.*;

  

class MaxRepeating {

  

    // Возвращает максимальный повторяющийся элемент в arr [0..n-1].

    // Элементы массива находятся в диапазоне от 0 до k-1

    static int maxRepeating(int arr[], int n, int k)

    {

        // Итерация по входному массиву для каждого элемента

        // arr [i], увеличиваем arr [arr [i]% k] на k

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

            arr[(arr[i]%k)] += k;

  

        // Находим индекс максимального повторяющегося элемента

        int max = arr[0], result = 0;

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

        {

            if (arr[i] > max)

            {

                max = arr[i];

                result = i;

            }

        }

  

        / * Раскомментируйте этот код, чтобы вернуть исходный массив

        для (int i = 0; i <n; i ++)

          arr [i] = arr [i]% k; * /

  

        // Возвращаем индекс максимального элемента

        return result;

    }

  

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

    public static void main (String[] args)

    {

  

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

        int n = arr.length;

        int k=8;

        System.out.println("Maximum repeating element is: " +

                           maxRepeating(arr,n,k));

    }

}
/ * Этот код предоставлен Девешом Агравалом * /

python3

# Python программа для поиска максимального повторяющегося числа

  
# Возвращает максимальный повторяющийся элемент в arr [0..n-1].
# Элементы массива находятся в диапазоне от 0 до k-1

def maxRepeating(arr, n,  k):

  

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

    # arr [i], увеличить arr [arr [i]% k] на k

    for i in range(0,  n):

        arr[arr[i]%k] += k

  

    # Найти индекс максимального повторяющегося элемента

    max = arr[0]

    result = 0

    for i in range(1, n):

      

        if arr[i] > max:

            max = arr[i]

            result = i

  

    # Раскомментируйте этот код, чтобы получить исходный массив

    # для i в диапазоне (0, n):

    # arr [i] = arr [i]% k

  

    # Возвращаем индекс максимального элемента

    return result

  

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

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

n = len(arr)

k = 8

print("The maximum repeating number is",maxRepeating(arr, n, k))

  
# Этот код предоставлен
# Смита Динеш Семвал

C #

// C # программа для поиска максимального повторения
// число

using System;

  

class GFG {

      

    // Возвращает максимально повторяющийся элемент

    // в обр [0..n-1].

    // Элементы массива находятся в диапазоне

    // от 0 до k-1

    static int maxRepeating(int []arr, 

                             int n, int k)

    {

        // Перебирать входной массив, для

        // каждый элемент arr [i], приращение

        // arr [arr [i]% k] от k

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

            arr[(arr[i]%k)] += k;

  

        // Находим индекс максимума

        // повторяющийся элемент

        int max = arr[0], result = 0;

          

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

        {

            if (arr[i] > max)

            {

                max = arr[i];

                result = i;

            }

        }

  

        // Возвращаем индекс

        // максимальный элемент

        return result;

    }

  

    / * Функция драйвера для проверки

     вышеуказанная функция * /

    public static void Main ()

    {

  

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

        int n = arr.Length;

        int k=8;

          

        Console.Write("Maximum repeating "

                          + "element is: " 

                  + maxRepeating(arr,n,k));

    }

}

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

PHP

<?php
// PHP программа для поиска
// максимальное количество повторений

  
// Возвращает максимум повторения
// элемент в arr [0..n-1].
// Элементы массива
// в диапазоне от 0 до k-1

function maxRepeating($arr, $n, $k)

{

      

    // Итерация по входному массиву,

    // для каждого элемента arr [i],

    // увеличиваем arr [arr [i]% k] на k

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

        $arr[$arr[$i] % $k] += $k;

  

        // Найти индекс

        // максимальное повторение

        // элемент

        $max = $arr[0];

        $result = 0;

    for ($i = 1; $i < $n; $i++)

    {

        if ($arr[$i] > $max)

        {

            $max = $arr[$i];

            $result = $i;

        }

    }

  

    / * Раскомментируйте этот код

       вернуть исходный массив

       для (int i = 0; i <n; i ++)

       arr [i] = arr [i]% k; * /

  

    // Возвращаем индекс

    // максимальный элемент

    return $result;

}

  

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

    $arr = array(2, 3, 3, 5, 3, 4, 1, 7);

    $n = sizeof($arr);

    $k = 8;

  

    echo "The maximum repeating number is ",

        maxRepeating($arr, $n, $k);

  
// Этот код предоставлен Аджитом
?>


Выход:

The maximum repeating number is 3

Упражнение:
Вышеупомянутое решение печатает только один повторяющийся элемент и не работает, если мы хотим напечатать все максимально повторяющиеся элементы. Например, если входной массив равен {2, 3, 2, 3}, вышеприведенное решение выведет только 3. Что если нам нужно напечатать оба из 2 и 3, так как оба они встречаются максимальное количество раз. Напишите O (n) время и O (1) функцию дополнительного пробела, которая печатает все максимально повторяющиеся элементы. (Подсказка: мы можем использовать максимальное отношение arr [i] / n вместо максимального значения в шаге 2).

Обратите внимание, что приведенные выше решения могут вызвать переполнение, если при многократном добавлении k значение становится больше, чем INT_MAX.

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

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

Найти максимальное число повторений в O (n) времени и O (1) лишних пробелах

0.00 (0%) 0 votes