Алгоритм проверки массива на отсутствие повторяющихся значений

← →
Urri (2003-11-10 12:47) [0]

Добрый день всем.

Имеется: несортированный одномерный массив значений.
Нужно: проверить его на наличие повторяющихся значений.
Подскажите алгоритм, пожалуйста, кто сталкивался.

Заранее спасибо.

← →
Mouse (2003-11-10 12:53) [1]

for i:=1 to massend do
begin
for k:=1 to massend do
if (i <> k) and (massiv[i] = massiv[k]) then // Найденно совпадание
end;
end;

← →
Urri (2003-11-10 12:58) [2]

Эээээ ... пошустрее бы.
Вроде где-то видел красивый способ, но может быть и ошибаюсь.

← →
mfender © (2003-11-10 12:59) [3]

А чем это не красиво и не шустро? Или массив гигабайтный? :))

← →
staryx (2003-11-10 13:01) [4]

Можно в 2 раза быстрее:
for i:=1 to massend do
begin
for k:=1 to i+1 do
if massiv[i] = massiv[k] then // Найденно совпадание
end;
end;

← →
Mouse (2003-11-10 13:02) [5]

Методов куча!,.. ты скажи что тебе надо конкретнее делать потом с результатом!

← →
Urri (2003-11-10 13:02) [6]

ну не мегабайтный, но приличный весьма ))
еще - массив из целых чисел, забыл сказать.

← →
Mouse (2003-11-10 13:03) [7]

можно даже так:
for i:=1 to massend do
begin
for k:= i to massend do
if (i <> k) and (massiv[i] = massiv[k]) then // Найденно совпадание
end;
end;
так шустрее!

← →
Urri (2003-11-10 13:03) [8]

надо просто факт - есть повторение или нет

← →
Mouse (2003-11-10 13:06) [9]

даже так:
for i:=1 to massend-1 do
begin
for k:=i+1 to massend do
if and massiv[i] = massiv[k] then // Найденно совпадание
end;
end;

Пишу на ходу!,.. проверяй на ошибки :-)

← →
staryx (2003-11-10 13:07) [10]

Если есть много памяти, то реализовать что-то типа сортировки вставками, т.е. методом половинного деления находим место вставки, проверяем, нет ли такого-же, вставляем. Если надо подробнее - попытаюсь...

← →
TUser © (2003-11-10 13:07) [11]

Можно разделить массив на несколько маленьких массивчиков (записать туда цифирь от 1 до 10, от 10 до 20 и т.д.). Тогда, если на единый массив надо времени n^2, то на разделение на маленькие - n (просмотреть весь массив), а накаждый из них потом уже по n^2/const. Хотя радикатьного ускорения это тебе не дасть - все равно O(n^2).
См. также www.algolist.manual.ru и faqs.org.ru

← →
Mouse (2003-11-10 13:08) [12]

and убери
if massiv[i] = massiv[k] then // Найденно совпадание

← →
Urri (2003-11-10 13:08) [13]

ok, спасибо, сделаем так пока, мож в дальнейшем озарение посетит :)))

← →
Mouse (2003-11-10 13:13) [14]

> staryx (10.11.03 13:07) [10]
> Если есть много памяти, то реализовать что-то типа сортировки
> вставками, т.е. методом половинного деления находим место
> вставки, проверяем, нет ли такого-же, вставляем. Если надо
> подробнее - попытаюсь...

Он же написал что массив несортированный

ты пока его отсортируешь.... сам понимаешь!,..
Надо просто сравнивать текушую ячейку со всеми последующими и так двигать текущую ячейку к концу массива!,..

Чем ближе к концу - тем быстрее он будет проверять!

Самое быстрое - сначала отсортировать к.-л. быстрым методом, а потом за один проход найти дубликат(ы)...

← →
Adoon (2003-11-10 14:27) [16]

Если я ошибаюсь - поправьте меня ( навеяно библиотекой STL ) - работает только если в Delphi можно узнать размер множества:
сделать один проход по массиву, занося в множество эти элементы
потом сравнить размеры массива и множества, если размеры множества (в библиотеке STL есть размер множества, а как в Delphi - не помню) меньше размеров массива, то были повторяющиеся элементы.

← →
Adoon (2003-11-10 14:35) [17]

Можно и без размеров обойтись:
на каждом этапе проверяем есть ли в множестве данный элемент,
если нет, то заносим его в это множество, иначе выходим из цикла и говорим, что у нас повторяющиеся элементы

← →
Urri (2003-11-10 14:46) [18]

в дельфях множество может только 256 ordinal значений включать

В Дельфи есть тип TBits заменитель множества на больших массивах, для мегабайтного массива потребуется 128кб, всяко быстрее двух циклов будет.

Алгоритм проверки массива на отсутствие повторяющихся значений Найти похожие ветки