Как мне найти режим отсортированного массива?

Question

Мне нужно написать функцию, чтобы найти режим массива. Однако я не умею придумывать алгоритмы и надеюсь, что кто-то другой знает, как это сделать.

Я знаю размер массива и значения в каждом элементе, и я отсортировал массив от наименьшего к наибольшему.

Массив

будет передан в функцию mode, как

mode = findMode (arrayPointer, sizePointer);

UPDATE:

После прочтения комментариев я попробовал это

int findMode(int *arrPTR, const int *sizePTR)
{
    int most_found_element = arrPTR[0];
    int most_found_element_count = 0;
    int current_element = arrPTR[0];
    int current_element_count = 0;
    int count;
    for (count = 0; count < *sizePTR; count++)
    {
        if(count == arrPTR[count])
             current_element_count++;
        else if(current_element_count > most_found_element)
        {
            most_found_element = current_element;
            most_found_element_count = current_element_count;
        }
        current_element = count;
        current_element_count=1;
    }

    return most_found_element;
}

У меня все еще есть проблемы с пониманием этого алгоритма, если кто-то может разобраться со мной. Я никогда не использовал векторы, поэтому не понимаю других примеров.

Answer 1

У вас есть почти все.

Вы можете воспользоваться тем, что массив отсортирован.

Просто просмотрите массив с отслеживанием как текущих равных последовательных чисел, так и наибольшего числа равных последовательных чисел, которые вы нашли до этой точки (и какое число произвело его ). В конце концов у вас будет наибольшее количество равных последовательных чисел, и какое число произвело его. Это будет режим.

Примечание: Для решения, которое не требует, чтобы массив был отсортирован, см., Например, один на основе гистограммы в связанный вопрос .

Answer 2

set most_found_element to the first element in the array
set most_found_element_count to zero
set current_element to the first element of the array
set current_element_count to zero
for each element e in the array
    if e is the same as the current_element
        increase current_element_count by one
    else
        if current_element_count is greater than most_found_element_count
            set most_found_element to the current_element
            set most_found_element_count to current_element_count
        set current_element to e
        set current_element_count to one
if current_element_count is greater than most_found_element_count
    set most_found_element to the current_element
    set most_found_element_count to current_element_count
print most_found_element and most_found_element_count

Я думал, что имена объяснят это, но здесь мы идем:

When we start, no element has been found the most times
  so the "high-score" count is zero.
Also, the "current" value is the first, but we haven't looked at it yet 
  so we've seen it zero times so far
Then we go through each element one by one
  if it's the same as "current" value, 
     then add this to the number of times we've seen the current value.
  if we've reached the next value, we've counted all of the "current" value.
     if there was more of the current value than the "high-score"
        then the "high-score" is now the current value
     and since we reached a new value
        the new current value is the value we just reached
Now that we've seen all of the elements, we have to check the last one
  if there was more of the current value than the "high-score"
    then the "high-score" is now the current value
Now the "high-score" holds the one that was in the array the most times!

Также обратите внимание: в моем исходном алгоритме / коде была ошибка, мы должны сделать дополнительную проверку «current» после окончания цикла, так как он никогда не находит «один после последнего».

Answer 3

Подсказки:

В: Как вы определяете режим?

A: Число, число которых в массиве наибольшее.

В: Как считать числа в упорядоченном массиве?

A: Итерация по массиву, и пока следующий элемент равен предыдущему, увеличьте счетчик для этого значения.

В: Если счет предыдущего значения меньше, чем счет текущего значения, то может ли предыдущее значение быть режимом?

A: Нет

Answer 4

Если входной массив отсортирован, здесь используется тот же подход, который описан в других ответах, но реализован по-другому, лучше и проще для понимания.

1. Запуск цикла над вводоммассив.
2. Сохранение значения глобального режима и счетчика режима.
3. Запуск скользящего окна до тех пор, пока вы не найдете равные элементы.
4. Если количество локальных равных элементов больше, чем общее количество режимов,затем обновите глобальный режим и счетчик режимов.

Вот рабочий и проверенный код в C++.

int mode(vector<int> a, int N)
{
    int mode = a[0];
    int mode_count = 1;
    int i = 0;
    while (i < N - 1) {
        int cur = a[i];
        int cur_count = 1;
        while (a[i] == a[i + 1]) {
            i++;
            cur_count++;
        }
        if (cur_count > mode_count) {
            mode_count = cur_count;
            mode = a[i];
        }
        i++;
    }
    return mode;
}