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

Question

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

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

массив будет передан функции, как режим

режим = 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

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! 

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

Answer 2

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

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

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

Примечание: Для решения, которое делает не требуется массив будет отсортирован, смотри, например, one based in the histogram approach в related question.

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; 
}