Светильники Вилед

Дана последовательность целых чисел. Найти количество различных чисел в этой последовательности. C++

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

Алгоритм

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

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

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

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

Реализация на C++

#include <unordered_set>
#include <iostream>

int main()
{
    std::unordered_set<int> set;
    int number;
    while (std::cin >> number)
    {
        set.insert(number);
    }
    std::cout << set.size() << std::endl;
    return 0;
}

В этой программе мы использовали класс std::unordered_set<int>, который предоставляет реализацию хеш-таблицы для хранения целых чисел. В цикле мы считываем числа из стандартного ввода и добавляем каждое число в хеш-таблицу с помощью метода insert(). После этого выводим размер хеш-таблицы, который и будет искомым количеством различных элементов в последовательности.

Заключение

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