Решение задачи методом хэш-таблиц или скип-листов

@dsfsdfds · Регистрация: 02.10.2020

Студворк — интернет-сервис помощи студентам

Условие
Дана последовательность целых чисел. Каждое прочитанное число обрабатывается следующим образом:
если число больше нуля, оно добавляется к текущему множеству чисел;
если число меньше нуля, противоположное ему число удаляется из текущего множества чисел;
если число равно нулю, множество чисел выводится в порядке возрастания и программа завершает работу.
Формат входного файла
Входной файл содержит последовательность чисел.
Формат выходного файла
Выходной файл должен содержать последовательность чисел, отсортированных по возрастанию.
Ограничения
Количество чисел находится в диапазоне от 0 до 10^6, сами числа — в диапазоне от  − 2^31 до 2^31 − 1.

Примечание: в этой редакции предлагается решать задачу с использованием скип-листов или хэш-таблиц.
Примеры теста:
Входной файл (input.txt) Выходной файл (output.txt)
3 2 1 3 0__________________1 2 3

@igorrr37 · 24.01.2021, 00:58

через стандартную хэш таблицу

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <algorithm>
#include <fstream>
#include <unordered_set>
#include <set>
#include <iomanip>
 
 
int main()
{
    std::ifstream ifs{"in.txt"};
    if (!ifs.is_open())
    {
        std::cerr << "Unable to open file\n";
        throw 1;
    }
    std::unordered_set<int> ust;
    int val{};
    while (ifs >> val)
    {
        if (val > 0)
        {
            ust.insert(val);
        }
        else if (val < 0)
        {
            ust.erase(-val);
        }
        else
        {
            std::set<int> sst{ ust.begin(), ust.end() };
            for (auto val : sst)
            {
                std::cout << std::setw(5) << std::left << val;
            }
            break;
        }
    }
 
    ifs.close();
}

IGPIGP · 24.01.2021, 04:17

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

Новые блоги и статьи Все статьи Все блоги /
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ

@dsfsdfds 0 / 0 / 0 Регистрация: 02.10.2020 Сообщений: 25

	Решение задачи методом хэш-таблиц или скип-листов 23.01.2021, 14:44. Показов 1375. Ответов 2 Метки нет (Все метки) Условие Дана последовательность целых чисел. Каждое прочитанное число обрабатывается следующим образом: если число больше нуля, оно добавляется к текущему множеству чисел; если число меньше нуля, противоположное ему число удаляется из текущего множества чисел; если число равно нулю, множество чисел выводится в порядке возрастания и программа завершает работу. Формат входного файла Входной файл содержит последовательность чисел. Формат выходного файла Выходной файл должен содержать последовательность чисел, отсортированных по возрастанию. Ограничения Количество чисел находится в диапазоне от 0 до 10^6, сами числа — в диапазоне от  − 2^31 до 2^31 − 1. Примечание: в этой редакции предлагается решать задачу с использованием скип-листов или хэш-таблиц. Примеры теста: Входной файл (input.txt) Выходной файл (output.txt) 3 2 1 3 0__________________1 2 3 0

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 9007 / 4708 / 630 Регистрация: 04.12.2011 Сообщений: 14,003 Записей в блоге: 16
	24.01.2021, 04:17
	dsfsdfds, глядя в пример видно что множества - без повторов. Странно, что такая важная деталь не оговорена явно. Особенно если учесть, что скип-листы и хеш-таблицы в типичных реализациях не ограничивают повторяемость, хотя разумеется, это можно сделать. Задача от рукокрылых небожителей) 0