Блог

Моя задача-найти наиболее повторяющийся элемент в массиве без сортировки или хэш-таблиц.

Это мой псевдокод:

 #include lt;stdio.hgt;   int most_frequent(int *a, int n) {  int i, j, max_element, count;  int maxcount = 0;   for(i = 0; ilt;n; i  )  {  count = 1;  for(j = i 1; jlt;n; j  )  {  if(a[j] == a[i])  {  count   ;  if(count gt; maxcount)  {  max_element = a[j];  }  }  }  }  return max_element; }  

Проблема в том, что он не всегда работает правильно, например, с массивом [1 1 2 2 3 3 3 4 4 4 4 5 5 7] результат будет 5 .

В этом заявлении if

 if(count gt; maxcount)  {  max_element = a[j];  }  

вы забыли изменить переменную maxcount

 if(count gt; maxcount)  {  maxcount = count;  max_element = a[j];  }  

Кроме того, оператор if должен быть перемещен ниже внутреннего цикла for.

 for(i = 0; ilt;n; i  ) {  count = 1;  for(j = i 1; jlt;n; j  )  {  if(a[j] == a[i])  {  count   ;  }   }   if(count gt; maxcount)  {  maxcount = count;  max_element = a[i];  }  }  

Обратите внимание, что если пользователь передаст функции значение параметра n, равное 0, то функция вернет неопределенное значение, поскольку переменная max_element не инициализирована.

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

 #include lt;stdio.hgt;  size_t most_frequent( const int *a, size_t n ) {  size_t pos = 0;  size_t max_count = 0;    for ( size_t i = 0; i lt; n - max_count; i   )  {  size_t count = 1;  for ( size_t j = i   1; j lt; n; j   )  {  if ( a[j] == a[i] )   count;  }    if ( max_count lt; count )  {  max_count = count;  pos = i;  }  }    return pos; }  int main( void )  {  int a[] = { 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 7 };  const size_t N = sizeof( a ) / sizeof( *a );   size_t pos = most_frequent( a, N );    printf( "The most frequent number is %d found at position %zun",   a[pos], pos );    return 0; }  

Вывод программы является

 The most frequent number is 4 found at position 7