2017-02-16 7 views
0

Я пытаюсь найти самый повторный номер int моего вектора. Вот мой код ...Как найти наиболее повторяющееся значение в массиве?

for(i=0; i < dim; i++){ 
     temp=vet[i]; 
    for(i=0; i < dim; i++){ 
     if(vet[i]==temp){ 
      count++; 
     } 
    } 
    if(most < count){ 
     most=count; 
     elem=vet[i]; 
    } 
} 
return elem;} 

Это не правильно .. Я надеюсь, что вы можете мне помочь .. Спасибо!

+0

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

+0

Я знаю, что случилось. Он не компилируется! –

+0

Для 'C' это довольно сложная проблема, вам нужен либо хороший алгоритм (сначала отсортируйте массив, затем используйте метод caterpillar), либо хорошую структуру данных (хеш-таблицу или словарь, например' Python'). –

ответ

2

Наиболее очевидная проблема заключается в том, что ваш код использует i как в внутренней, так и в внешней петлях. Переменные most и count неинициализированы в приведенном выше коде, и count необходимо сбрасывать перед запуском внутреннего цикла каждый раз.

Метод, используемый в этом коде итерации по всему массиву для каждого элемента для подсчета видимости, не очень эффективен. Эффективность можно было бы улучшить, запустив внутренний цикл от i + 1, а не от 0. Таким образом, первое количество частот для каждого элемента будет правильным, хотя более поздние значения будут низкими, поскольку более ранние индексы не будут посещаться. Но это не имеет значения, так как первый счетчик, если возможно, установил переменную most. Переменная count может быть установлена ​​на 1 до начала внутреннего цикла, так как значение i-го элемента является тестовым значением, а внутренний цикл пропускает этот индекс. Это изменение существенно уменьшит количество обращений к массиву.

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

int get_most_common(int vet[], size_t dim) 
{ 
    size_t i, j, count; 
    size_t most = 0; 
    int temp, elem; 

    for(i = 0; i < dim; i++) { 
     temp = vet[i]; 
     count = 1; 
     for(j = i + 1; j < dim; j++) { 
      if(vet[j] == temp) { 
       count++; 
      } 
     } 
     if (most < count) { 
      most = count; 
      elem = vet[i]; 
     } 
    } 
    return elem; 
} 
+0

Может ли внутренний цикл начинаться с 'i + 1', если вы установите' count = 1; '(потому что' temp' содержит первое значение подсчитываемого набора)? Мне жаль продолжать рассказывать все. –

+0

@ JonathanLeffler-- ответ обновлен. Спасибо за предложение. –

0

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

Чтобы реализовать полную версию такой функции с эффективностью, вам понадобится специальная структура данных, такая как hashtable или dictionary.

Но следующие коды работают хорошо, если вам просто нужно вернуть первый элемент, соответствующий этому условию.

#include <stdio.h> 

// returns the first matched most frequent item of a list 
// list items of same value must be grouped, for example, a sorted list 
// only returns the first matched item 
int max_frequent_item_of(int vet[], int dim) 
{ 
    int i = 0; 
    // element and its count of current sublist 
    int current = vet[0]; 
    int current_count = 0; 
    // most frequent element and its count of the list so far 
    int most = vet[0]; 
    int most_count = 0; 
    while (i < dim) { 
    // if i-th element still belong to current sublist, run the counter 
    if (vet[i] == current) { 
     current_count += 1; 
     i += 1; 
    } 
    // otherwise, the current sublist just ended 
    else { 
     // update the most frequent element 
     if (current_count > most_count) { 
     most = current; 
     most_count = current_count; 
     } 
     // reset current sublist 
     current = vet[i]; 
     current_count = 1; 
     i += 1; 
    } 
    } 
    printf("most frequent item %d, count %d\n", most, most_count); 
    return most; 
} 

int main(void) 
{ 
    // vet must be in order, sort with `qsort` if necessary 
    int vet[] = {1, 1, 2, 3, 4, 4, 4, 8, 9, 9}; 
    int size = 10; 
    int n; 
    printf("list: "); 
    for (n = 0 ; n < size; n++) 
    { 
     printf("%d ", vet[n]); 
    } 
    printf("\n"); 
    max_frequent_item_of(vet, size); 
    return 0; 
} 

выход

list: 1 1 2 3 4 4 4 8 9 9 
most frequent item 4, count 3 
+0

С сортировкой O (N log N), а это O (N), если массив можно упорядочить, это дает общую производительность O (N log N) и O (N) при поиске. Либо лучше, чем O (N^2) при достаточно больших N. –