Позиция элемента в списке

@smartes · Регистрация: 12.04.2013

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

Собственно задача у меня такая. Имеется массив А длинны около 1 000 000, заполненный intами. Программа находит числа из массива А и мне необходимо "пометить" что я уже нашел это число. Самым простым я нашел для себя представить А как массив из двух строк, где первая это сами числа, а вторая содержит 0 если еще мы не нашли число из соответствующей колонки, и 1 в противном случае.
Очевидно что если бы мне надо было определить один раз то цикл был бы вполне приемлем, на надо пройти все числа из списка.
Прочитал про такую штуку как unordered_set, мне кажется это может быть решением проблемы времени. Но к сожалению не разобрался как его применять.
Может кто набросает примерный код?

@ReDoX · 23.06.2018, 18:04

В чем проблема?

C++

  unordered_set<int> a;
 
  // цикл для прохода по списку
  // ...
  // в нем условие
  // если нужно число найдено, то...
  a.insert(found_number);
  
  // проход по этим числам
   for (const auto& i : a)

@smartes · 23.06.2018, 18:59 **[ТС]**

вся соль в том если использоваьб //цикл прохода по списки мне необходимо 1 000 000 х 1 000 000 итераций (в худшем случае). Моя идея была отказаться от этого цикла. на сколько я понял при помощи хеш и unordered_set я как раз могу получить позицию числа в в массиве (тем самым отказавшись от цикла).

@smartes 0 / 0 / 0 Регистрация: 12.04.2013 Сообщений: 42
		1
	Позиция элемента в списке 23.06.2018, 17:35. Показов 1731. Ответов 2 Метки нет (Все метки) Собственно задача у меня такая. Имеется массив А длинны около 1 000 000, заполненный intами. Программа находит числа из массива А и мне необходимо "пометить" что я уже нашел это число. Самым простым я нашел для себя представить А как массив из двух строк, где первая это сами числа, а вторая содержит 0 если еще мы не нашли число из соответствующей колонки, и 1 в противном случае. Очевидно что если бы мне надо было определить один раз то цикл был бы вполне приемлем, на надо пройти все числа из списка. Прочитал про такую штуку как unordered_set, мне кажется это может быть решением проблемы времени. Но к сожалению не разобрался как его применять. Может кто набросает примерный код? 0

@smartes 0 / 0 / 0 Регистрация: 12.04.2013 Сообщений: 42
	23.06.2018, 18:59 [ТС]	3
	вся соль в том если использоваьб //цикл прохода по списки мне необходимо 1 000 000 х 1 000 000 итераций (в худшем случае). Моя идея была отказаться от этого цикла. на сколько я понял при помощи хеш и unordered_set я как раз могу получить позицию числа в в массиве (тем самым отказавшись от цикла). 0

Позиция элемента в списке

Решение