Макс показывает число в двумерном массиве

У меня есть двумерный массив, и я знаю:

  • Количество строк и длина каждой строки
  • Каждая строка содержит только положительные числа
  • Каждая строка отсортирована
  • не использовать со вспомогательным массивом - не использовать со структурами данных

Требуемый выход

Мне нужно вернуть число, которое появляется максимальное количество раз во всем массиве эффективным способом. Я уже пытался передать весь массив, но это не эффективно.

Это пример массива.

{
  {5, 7, 8},
  {6, 6},
  {null},
  {5, 6, 8, 9}
}

Ожидаемое возвращаемое значение для этого примера - 6.

Я хотел бы получить объяснение или код на C++

Спасибо

Источник

4 ответа

Решение

Поскольку требуется решение C/C++, можно использовать 2D-массив. Все пропущенные значения могут быть представлены -1 (или любым числом, которое не ожидается в действительных числах, участвующих в поиске). Таким образом, пустая строка может быть представлена ​​всеми -1. Смотрите код ниже. Поскольку в C / C++ 2D массив постоянно представлен в памяти. Таким образом, мы можем конвертировать 2D массив в 1D массив. Теперь мы можем отсортировать массив. После сортировки все "-1" будут в начале, которые могут быть отброшены. Из оставшихся элементов мы можем найти максимальную частоту элемента.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int main()
{
    int i, prev, max = -1, count = 0, maxvalue = -1;
    int a[4][4] = {{5, 7, 8, -1}, {6, 6, -1, -1}, {-1, -1, -1, -1}, {5, 6, 8, 9}};
    //int a[4][4] = {{-1, -1, -1, -1}, {-1, -1, -1, -1}, {-1, -1, -1, -1}, {-1, -1, -1, -1}};

    int *b = (int*)a;
    int total = sizeof(a) / sizeof(int);

    qsort(b, total, sizeof(int), compare);

    for(i = 0; i < total; ++i)
    {
            if(b[i] != -1)
            {
                    break;
            }
    }

    //printf("\n");

    i = i + 1;

    prev = -1;
    count = 0;
    if(i < total)
    {
            prev = b[i];
            count = 1;
    }
    for(i = i + 1; i < total; ++i)
    {
            //printf("prev=%d, b[i]=%d, max=%d, count=%d\n", prev, b[i], max, count);

            if(prev == b[i])
            {
                    count++;;
            }
            else
            {
                    if(max < count)
                    {
                            max = count;
                            maxvalue = prev;
                    }
                    prev = b[i];
                    count = 1;
            }
    }

    if(max != -1)
    {
            printf("Max Occurence of %d = %d\n", maxvalue, max);
    }
    else
    {
            printf("All the rows are of zero length\n");
    }

    return 0;
}
//Output:
Max Occurence of 6 = 3
Источник

Вы можете использовать карту, чтобы отслеживать количество повторов и текущий максимум.

map<int, int> temp;
int currentMax= -999999,maxCount=0;
for(i=0; i< numberOflines ;i++)
{
        for(j=0;j< array[i].length;j++)
        {
            int newCount = ++temp[array[i][j]];
            if (maxCount < newCount) {
                 maxCount = newCount;
                 currentMax = array[i][j];
            }
        }
}
Источник

Для подсчета количества раз, когда элемент встречается в массиве, аналогичный вопрос с использованием рекурсии показан здесь.

Поскольку вы упомянули эффективность, было бы полезно отсортировать массив в порядке возрастания или убывания, прежде чем подсчитать, сколько раз элемент присутствует в массиве (если он не отсортирован). Хотя для небольшого размера ввода, как показано в вашем примере, это не будет иметь большого значения.

Источник

Во-первых, ваш ввод недопустим:

{
    {5, 7, 8},
    {6, 6},
    {null},
    {5, 6, 8, 9}
}

null не определяется C++, и даже если бы он был определен как 0, он должен интерпретироваться как int(0), а не пустой массив, как я думаю, что вы хотели.

Я предполагаю, что ввод, который вы намереваетесь подразумевать, должен выглядеть примерно так:

const initializer_list<int> a[] = {{5, 7, 8}, 
                                   {6, 6},
                                   {},
                                   {5, 6, 8, 9}};

Вам нужно будет поддерживать общее количество для каждого числа в любом массиве. Лучший способ сделать это - использовать map<int, int> totals который будет построен только с точным числом pairс, как есть уникальные элементы в a, Второй элемент каждого pair будет счетчик этого элемента, увиденного до сих пор. Вы можете заполнить его, выполнив:

for(const auto& i : a) for_each(cbegin(i), cend(i), [&](const auto& it){ totals[it]++;});

однажды totals заполнено, вам нужно только найти его наибольшее значение:

cout << max_element(cbegin(totals), cend(totals), [](const auto& lhs, const auto& rhs){return lhs.second < rhs.second;})->first << endl;

Живой пример

Источник
Другие вопросы по тегам