Задачи из книги Шеня

@Pinokio · Регистрация: 14.09.2012

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

Решил прорешать задачи из книги Шеня. Вот столкнулся со следующей и что-то не могу придумать алгоритм, помогите кто чем может

1.2.9. Та же задача, если известно, что все элементы массива - числа от 1 до k и число действий должно быть порядка n+k.

(та же задача - имеется в виду 1.2.7. Дан массив x: array [1..n] of integer. Найти коли-
чество различных чисел среди элементов этого массива. (Число
действий должно быть порядка n*n.))
С Уважением, Pinokio

@palva · 13.02.2013, 18:20

Заводим булевский массив b длины k. Сначала все его элементы устанавливаем в false (k операций). Потом просматриваем основной массив a и устанавливаем в true элементы b[a[i]] (n операций). Потом подсчитываем число true в массиве b (k операций).

@Pinokio 2 / 2 / 1 Регистрация: 14.09.2012 Сообщений: 83
		1
	Задачи из книги Шеня 13.02.2013, 18:03. Показов 1002. Ответов 1 Метки нет (Все метки) Решил прорешать задачи из книги Шеня. Вот столкнулся со следующей и что-то не могу придумать алгоритм, помогите кто чем может 1.2.9. Та же задача, если известно, что все элементы массива - числа от 1 до k и число действий должно быть порядка n+k. (та же задача - имеется в виду 1.2.7. Дан массив x: array [1..n] of integer. Найти коли- чество различных чисел среди элементов этого массива. (Число действий должно быть порядка n*n.)) С Уважением, Pinokio 0

@palva 4241 / 2938 / 687 Регистрация: 08.06.2007 Сообщений: 9,817 Записей в блоге: 4
	13.02.2013, 18:20	2
	Заводим булевский массив b длины k. Сначала все его элементы устанавливаем в false (k операций). Потом просматриваем основной массив a и устанавливаем в true элементы b[a[i]] (n операций). Потом подсчитываем число true в массиве b (k операций). 0