C получить режим из списка целых чисел

Question

Мне нужно написать программу, чтобы найти режим. Или наибольшее вхождение целого числа или целых чисел. Таким образом,

1,2,3,4,1,10,4,23,12,4,1 будет иметь режимы 1 и 4.

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

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

Так что, если бы у меня было то же самое сверху. Переберите 1,2,3,4,1,10,4,23,12,4,1

Тогда список пуст, поэтому добавьте узел с номером = 1 и значением = 1. 2 не существует, поэтому добавьте узел с номером = 2 и значением = 1 и так далее. Получить до 1 и 1 уже существует, поэтому значение = 2 сейчас.

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

Как только я закончу, просмотрите связанный список и создайте новый связанный список, который будет содержать режимы. Итак, я установил заголовок для первого элемента, который равен 1. Затем я просматриваю связанный список, содержащий события, и сравниваю значения. Если вхождения текущего узла> текущего максимума, тогда я устанавливаю голову этому узлу. Если его = к самому высокому, тогда я добавляю узел в связанный список режимов.

Как только я закончу, я перебираю список режимов и печатаю значения.

Не уверен, что это сработает. Кто-нибудь видит что-то не так с этим? Есть ли более простой способ сделать это? Я тоже думал о хеш-таблице, но не совсем уверен, как это сделать в C.

Спасибо.

Answer 1

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

Answer 2

Алгоритм, который у вас есть, подходит для домашнего задания.Для оптимизации кода можно сделать множество вещей, например:

• использовать двоичное дерево для эффективности,
• использовать массив счетчиков, где индекс - это число(при условии, что диапазон номеров ограничен).

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

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

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

typedef struct sElement {
    int number;
    int count;
    struct sElement *next;
} tElement;
tElement first = NULL;

Затем создайте несколько функций для создания и использования списка:

tElement *incrementElement (int number);
tElement *getMaxCountElement (void);
tElement *getNextMatching (tElement *ptr, int count);

Эти функции будут соответственно:

• Увеличиватьсчитать для элемента (или создать его и установить для счетчика 1).
• Сканировать все элементы, возвращающие максимальное количество.
• Получить указатель следующего элемента, соответствующий количеству, начиная с заданной точкиили NULL, если не больше.

Псевдокод для каждого:

def incrementElement (number):
    # Find matching number in list or NULL.

    set ptr to first
    while ptr is not NULL:
        if ptr->number is equal to number:
            return ptr
        set ptr to ptr->next

    # If not found, add one at start with zero count.

    if ptr is NULL:
        set ptr to newly allocated element
        set ptr->number to number
        set ptr->count to 0
        set ptr->next to first
        set first to ptr            

    # Increment count.

    set ptr->count to ptr->count + 1

def getMaxCountElement (number):
    # List empty, no mode.

    if first is NULL:
        return NULL

    # Assume first element is mode to start with.

    set retptr to first

    # Process all other elements.

    set ptr to first->next
    while ptr is not NULL:
        # Save new mode if you find one.

        if ptr->count is greater than retptr->count:
            set retptr to ptr
        set ptr to ptr->next

    # Return actual mode element pointer.

    return retptr

def getNextMatching (ptr, number):
    # Process all elements.

    while ptr is not NULL:
        # If match on count, return it.

        if ptr->number is equal to number:
            return ptr
        set ptr to ptr->next

    # Went through whole list with no match, return NULL.

    return NULL

Тогда ваша основная программа становится:

# Process all the numbers, adding to (or incrementing in) list .

for each n in numbers to process:
    incrementElement (n)

# Get the mode quantity, only look for modes if list was non-empty.

maxElem = getMaxCountElement ()
if maxElem is not NULL:
    # Find the first one, whil exists, print and find the next one.

    ptr = getNextMatching (first, maxElem->count)
    while ptr is not NULL:
        print ptr->number
        ptr = getNextMatching (ptr->next, maxElem->count)

Answer 3

Я бы выбрал простое решение для хеш-таблицы .

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

struct ItemFreq {
    struct ItemFreq * next_;
    int    number_;
    int    frequency_;
};

Обработка начинается с

max_freq_so_far = 0;

Проходит список номеров. Для каждого number в хеш-таблице ищется элемент ItemFreq x, такой что x.number_ == number.

• Если такого x не найдено, то элемент ItemFreq создается как { number_ = number, frequency_ = 1} и вставляется в хеш-таблицу.
• Если какой-то x был найден, то его frequency_ увеличивается.
• Если frequency_ > max_freq_so_far, то max_freq_so_far = frequency

Обойдя список завершенных чисел, мы просматриваем хеш-таблицу и печатаем ItemFreq элементов, чьи frequency_ == max_freq_so_far

Сложность алгоритма: O(N), где N - количество элементов в списке ввода.

Для простой и элегантной конструкции хеш-таблицы см. раздел 6.6 из K & R (язык программирования C) .

Answer 4

Если диапазон чисел известен заранее и является разумным числом, вы можете выделить достаточно большой массив для счетчиков и просто набрать count[i] += 1.

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

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

Answer 5

Этот ответ является примером идеи Пола Кулиневича:

int CompInt(const void* ptr1, const void* ptr2) {
  const int a = *(int*)ptr1;
  const int b = *(int*)ptr2;
  if (a < b) return -1;
  if (a > b) return +1;
  return 0;
}

// This function leave the modes in output and return the number
// of modes in output. The output pointer should be available to
// hold at least n integers.
int GetModes(const int* v, int n, int* output) {
  // Sort the data and initialize the best result.
  qsort(v, v + n, CompInt);
  int outputSize = 0;

  // Loop through elements while there are not exhausted.
  // (look there is no ++i after each iteration).
  for (int i = 0; i < n;) {
    // This is the begin of the new group.
    const int begin = i;

    // Move the pointer until there are no more equal elements.
    for (; i < n && v[i] == v[begin]; ++i);

    // This is one-past the last element in the current group.
    const int end = i;

    // Update the best mode found until now.
    if (end - begin > best) {
      best = end - begin;
      outputSize = 0;
    }
    if (end - begin == best)
      output[outputSize++] = v[begin];
  }
  return outputSize;
}