Эту задачу вам могут предложить решить во время собеседования при устройстве на работу.
Дан байтовый массив 100 на 100. Предложите самый быстрый алгоритм, который бы определял есть ли в этом массиве совпадающие элементы.
update
Первым правильно ответил Вячеслав.Ответ
В одном байте можно закодировать 256 значений, а в массиве их должно быть 10000, поэтому совпадения будут в любом случае. Программа не нужна.
Головоломка археолога.
Головоломка филателиста.
Головоломка нумизмата.
Завести вспомогательный битовый массив длины 256, в который заносить, встречалось ли уже в основном массиве данное значение байта. Конкретно, если X[A[I,J]]=0, то X[A[I,J]]:=1 и перейти к следующему A[I,J]. Если же X[A[I,J]]=1, то в исходном массиве есть повторяющиеся элементы.
ОтветитьУдалитьМожет быть будут еще варианты?
ОтветитьУдалитьМожет, и будут, но этот вариант требует одного прохода по массиву, а меньше точно не получится.
ОтветитьУдалитьХм)) Ну так как различных байтов 256, а в массиве 10000 элементов, то самый быстрый алгоритм проверки состоит из одной операции - return true :)
ОтветитьУдалитьЗадачка конечно была с подвохом :) Совпадение будет в любом случае, проверять не нужно.
ОтветитьУдалить