e-olymp 7847. Кількість різних елементів

Задача

Дано масив з [latex]N[/latex] цілих чисел. Визначте, скільки в цьому масиві різних елементів.

Вхідні дані

В першому рядку записано число [latex]N[/latex]. В наступному рядку записано [latex]N[/latex] цілих чисел. Всі числа за модулем не перевищують [latex]100[/latex].

Вихідні дані

Кількість різних елементів в масиві.

Тести

 

Вхідні дані Вихідні дані
1. 7
3 5 -7 7 5 -9 -4
6
2. 5
1 25 59 75 100
5
3. 6
1 2 3 1 2 4
4

Код 1

Код 1(without break)

Решение

Ставим отметку числу как будто видим его впервые.
Далее задача пройти по всем предыдущим числам и проверить не встретится ли такое же число.
Если встретится, то отметку снимаем, а пройдя по всем предыдущим числам так и не встретив числа равного текущему, значит «видим его впервые» и отметка поставлена справедливо.
Считаем количество отметок.

Ссылки

Код 2

Решение

Сначала, предположим, что все числа разные. Т.е. количество различных чисел равно [latex]n.[/latex] Далее в цикле for отметим читаем числа из потока и отмечаем в векторе vector<bool> a, что число встретилось. Встретив число ранее уже отмеченное уменьшаем счетчик различных чисел.

Ссылки

9 thoughts on “e-olymp 7847. Кількість різних елементів

    • Пожалуйста, сохраняйте в работе язык оригинала.
    • Используйте для заголовков H1 и H2 для подзаголовков. Если они есть.
    • Меток нет.
    • Категория не указана.
    • Зачем такое количество пустых строк? Ну, в коде — понятно, а по тексту их быть не должно. Если нужен вертикальный отступ, то в заголовках он есть.
    • Не стоит использовать буквы кириллицы в адресе публикации.
    • В условии не сказано сколько может быть чисел. С чего Вы взяли, что массива на 101 элемент будет достаточно? Его и недостаточно.
    • Вы не знаете сколько будет чисел, но знаете что сами числа не меньше чем -100 и не больше чем 100. Сколько же среди них может быть различных? не больше чем 201. Вот такой массив создать можно. Например массив логических значений — встретилось ли такое число или нет.
    • Еще раз повторяю. Во входном потоке может быть СКОЛЬ УГОДНО МНОГО чисел. Автор не делает ограничений на переменную $N$. Вы прошлый раз предположили, что $N$ не больше 100. Сейчас — 201. Я, конечно добавлю в какой-нибудь тест 1000 нулей, но не проще ли прочитать мой предыдущий комментарий внимательно?
      Если задачу на 201 различное число решить сразу сложно, предлагаю сначала решить следующую:
      Маше на Новый Год подарили пакет с некоторым количеством конфет. Известно, что мамин профком закупил для подарков шоколадные, карамельные и леденцы. Как Маше узнать сколько из этих трёх типов конфет встретились в ее пакете? При этом известно, что Маша еще маленькая и умеет только есть конфеты и считать до трёх.

    • Нет. Совсем даже не исправил.
      Вы опять предлагаете решение квадратичной сложностью. Нельзя запоминать все элементы и сравнивать каждый с каждым. Вам нужно полностью поменять концепцию.
      Видимо на конфетах плохо получилось объяснить или Вы эту часть моего моего комментария проигнорировали.
      Попытка №2. Решите задачу.
      Вам в течение часа с невероятной скоростью сообщают какие-то цифры. В конце этого часа Вам необходимо мгновенно ответить на вопрос — какие цифры ни разу не встретились. При этом у вас нет ни бумаги ни карандаша. Есть только две руки с пятью гибкими пальцами на каждой.
      P.S. Кажется теперь Вам не увернуться и придется изобрести правильный алгоритм

  1. Нет. Совсем даже не исправил.
    Вы опять предлагаете решение квадратичной сложностью. Нельзя запоминать все элементы и сравнивать каждый с каждым. Вам нужно полностью поменять концепцию.
    Видимо на конфетах плохо получилось объяснить или Вы эту часть моего моего комментария проигнорировали.
    Попытка №2. Решите задачу.
    Вам в течение часа с невероятной скоростью сообщают какие-то цифры. В конце этого часа Вам необходимо мгновенно ответить на вопрос — какие цифры ни разу не встретились. При этом у вас нет ни бумаги ни карандаша. Есть только две руки с пятью гибкими пальцами на каждой.
    P.S. Кажется теперь Вам не увернуться и придется изобрести правильный алгоритм

    • Добавил ещё один вариант решения.

    1. В условии переменные оформите в laTeX.
    2. Подумайте, как избавиться от brake в первом коде.
    3. 6-я строка второго кода. Вы хотели инициализировать ВЕСЬ массив. Но ваш способ задает значение первого элемента массива. Остальные получают случайные значения. При первом запуске все вероятно будет хорошо, но это недопустимая практика. Хотите автоматическую инициализацию нулями — определите массив вне функций. Но само решение мне нравится. Правильный подход.
      И есть вопрос. С какой целью Вы так сильно растягиваете код пустыми строчками? Мне кажется его не очень удобно читать. а вам?
  2. Всё, сдаюсь. Исправил последний код, завел его на ideone.com, поставил ссылку на него, написал объяснение, удалил все nbsp. Конечно, логично было бы все писать на украинском, раз начали на украинском. Но, нет, переводить не буду.
    Зачтено, молодец. Марафон длинною в полгода успешно завершен.

    P.S. Я всего-то надеялся увидеть дюжину строчек в типа

Добавить комментарий