Не могу придумать алгоритм((( помогите пожайлуста

[Бракозябр]

Здравствуйте!!!
У меня в общем вопрос. Никак вот не могу придумать алгоритм для решения задачи(((
Есть массив, заполненный литерами, скажем размером в 100 элементов. Как мне оставить литеры, которые входят один раз?
Была идейка - ввести новый массив из 256 элементов-счетчиков каждого элемента, и далее выводить те литеры, которые повторяются один раз, а литеры, повторяющиеся несколько раз, пускать еще на одну обработку. Но нужен другой алгоритм (увы, так сложилось). Помогите советом пожайлуста. 

[Scorp__)]

Бракозябр, нет памяти, значит надо тратить процессорное время.
Считываем первый элемент и просматриваем массив на предмет совпадений. Совпадений нет - в массив результатов, есть - к следующему элементу.
Считываем очередной элемент, повторяем процесс и так до конца массива.

Два цикла один в другом + массив результатов.

[Бракозябр]

Спасибо, Scorp__)  ))))

[Finch]

Если хотим выигрыш и по скорости, и при этом не важно первоначальное состояние массива. Можно сделать сортировку, а потом просто пройтись по отсортированному массиву.

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

[Scorp__)]

Finch, хорошее дополнение. Выигрыш получится O(log(n) + n) против O(n^2). Если я ничего не напутал.

[Serg79]

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

Кстати, при размере массива в 100 элементов, пузырьковая сорнтровка не проигрывает по своему быстродействию с быстрой.

[Finch]

Serg79, Я думаю, что 800 проходов при сортировке против 10000 есть разница. Другое дело, что при таком размере массива и при таких скоростях это не столь сушественно. А почему не пузырёк. потому что при проходе пузырьком по массиву мы получим примерно такой же расход времени, который получается в алгоритме  указанном Scorp__)

[Sla]

если массив "литерный", то можно попытаться построить разреженый массив
каждую "литеру" на свое место в массиве
типа
заполняем arraySort нулями
затем цикл по литерному массиву

Код:

arraySort[ord(mass[i])]:=1;

индекс arraySort код "литеры"

[Vlaor]

Была идейка - ввести новый массив из 256 элементов-счетчиков каждого элемента, и далее выводить те литеры, которые повторяются один раз, а литеры, повторяющиеся несколько раз, пускать еще на одну обработку.. 

Что-то я не понял, зачем создавать массив счетчиков если необходимо лишь определить двойное вхождение элемента. Для этого достаточно одного бита на элемент?

[Бракозябр]

Уважаемый Vlaor, просто я посчитал в начале сделать алгоритм меньшей сложности и додумался только до массива счетчиков. Ведь нужен был алгоритм с малой сложностью. Если не вру с массивом счетчиков она линейная (прошу палками не бить, плохо пока в это разбираюсь). Но, увы, алгоритм пришлось поменять на более жесткий в плане сложности. В ответ хочу задать вопрос (просто не совсем понял):
  "Для этого достаточно одного бита на элемент?" Расскажите подробней)))

[Алексей++]

Бракозябр, Vlaor  имеет в виду битовый массив вместо массива счётчиков ) Быстродействие чуть пониже, но памяти на такий "массив флажков" уйдёт в 8 раз меньше. А счётчики там считают от 0 до 1 , но для этой задачи этого вполне достаточно

индекс бита вычислять так  -
номер байта == N/8
номер бита в байте == N%8 (маска == (1<<N%8))

[Starech]

А не проще: взять первый элемент искать схожие в массиве и если таковые есть удалять вместе с этим элементом, в конце останутся только нужные!

[Starech]

Блин забыл, взять второй элемент... третий...

[Sands]

Starech А чем предложенній тобой алгоритм лучше предложенного изначально Scorp_)-ом?

[Starech]

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

[Starech]

После завершения программы в BH находиться кол-во оставшихся эл-тов,
а в BUFFER сам массив эл-тов, затирки ненужных байтов нет, поэтому при просмотре
в отладчике там по всему якобы "массиву" разбросаны эл-ты бывшего массива
поэтому и надо было в BH оставлять кол-во оставшихся эл-тов!


START:
    lea di,BUFFER
    mov bh,100       ; кол-во эл-тов
    mov bl,1       ; проверяемый эл-т
    xor ch,ch

CIKL_1:
    lea di,BUFFER
    xor ah,ah
    mov al,bl
    add di,ax
    mov cl,bh
    jcxz EXIT_PR    ; выходим если эл-тов не осталось
    sub cl,bl       ; кол-во проверяемых эл-тов
    jc EXIT_PR       ; выходим если проверяемый эл-т = кол-ву оставшихся
    mov al,[di-1]   ; байт для проверки
    push di
    cld
    repne scasb       ; ищем подобный
    jnz SL_EL
    dec di
    mov dx,di       ; сохраняем di в dx
    pop di       ; востанавливаем начальное значение
    push cx       ; сохраняем cx
    mov si,di
    inc si       ;
    mov cl,bh
    sub cl,bl
    rep movsb       ; сдвигаем весь массив на байт
    dec bh       ; массив уменьшился
    pop cx
    mov di,dx
    jmp DALEE       ; переход на вторую процедуру


; вторая часть программы

OSN_CIKL:
    repne scasb       ; ищем подобный элемент
    jnz CIKL_1      ; нет, переходим к следующему элементу
    ; mov dx,di

DALEE:
    push di
    mov si,di       ; копируем его в si и dx

CIKL_3:
    jcxz EXIT_SL    ; проверяем на конец массива да! - выходим
    scasb       ; нет проверяем следующий эл-т
    jnz ROLLING     ; не подобный на сдвиг массива
    inc si       ; подобный увеличиваем значение элемента для сдвига
    dec bh
    dec cx       ; уменьшаем значение счётчика
    jmp CIKL_3

ROLLING:
    pop di       ; восстанавливаем адрес эл-та куда будем сдвигать
    push di
    dec di
    push cx       ; сохраняем счётчик
    rep movsb       ; сдвигаем
    pop cx
    pop di
    jmp OSN_CIKL

EXIT_SL:
    dec bh       ; массив на один эл-т уменьшился!
    pop di
    jmp CIKL_1

SL_EL:
    pop di
    inc di
    inc bl          ; следующий элемент
    jmp CIKL_1

EXIT_PR:
    ret          ; здесь может находиться процедура вывода на монитор

BUFFER   db 1, 8 dup 17, 38, 17, 20 dup 7, 69 dup (?)
CODESG   ends
end



Честно говоря фигни наворотил... наверно...