Алгоритъм за намиране на взаимно име в списъци

Четох Алгоритми от книгата Алгоритми на Робърт Седжуик и за известно време бях заседнал върху проблем с упражнения. Ето го въпроса:

Дадени са 3 списъка с N имена всеки, намерете алгоритъм, за да определите дали има общо име за трите списъка. Алгоритъмът трябва да има O(NlogN) сложност. Имате право да използвате само алгоритми за сортиране и единствените структури от данни, които можете да използвате, са стекове и опашки.

Реших, че мога да разреша този проблем с помощта на HashMap, но въпросите ни ограничават да го направим. Дори тогава това все още няма да има сложност на NlogN.


sorting algorithm
person Nick Chris    schedule 28.09.2012    source източник
comment
Това вероятно е по-подходящо за programmers.stackexchange.com: programmers.stackexchange.com/faq   -  person Craig Treptow    schedule 28.09.2012
comment
как би помогнало комбинирането им?   -  person Nick Chris    schedule 28.09.2012
comment
@CraigTreptow - Това е програмен въпрос, така че защо не е разрешено тук?   -  person Nick Chris    schedule 28.09.2012
comment
Ако комбинирате списъците, сортирате ги и търсите 3 последователни имена (ако приемем, че всеки списък може да има име най-много 1 път).   -  person Dan W    schedule 28.09.2012
comment
@Nick Chris - добре, мисълта ми беше, че това е въпрос за алгоритъм, както е споменато в ЧЗВ за програмисти   -  person Craig Treptow    schedule 28.09.2012
comment
Тъй като те са списъци, а не набори, мисля, че не можете да приемете, че списъкът може да има име само веднъж.   -  person ajon    schedule 28.09.2012
comment

Работя върху някакъв код в Lua и продължавам да получавам тази грешка, въпреки че е дефинирана.

Казва се, че „LM“ е нулева стойност, когато очевидно не е, тъй като LM = {} е първото нещо, което имам в моя код. Използвам тази таблица за функции.

LM = {}
LM.Classes = {}
LM.Factions = {}
LM.Items = {}
LM.Core = {}
LM.Ent = {}
LM.GUI = {}
LM.Core.ValidLMEntities = {
                "fm_item",
                "fm_keys",
                "fm_fists",
                "fm_money",
                }

function LM.Core.IsLMEntity(ent)    
    return IsValid(ent) && table.HasValue(LM.Core.ValidLMEntities, ent:GetClass())
end

Съобщение за грешка:

[ERROR]
gamemodes/lemonmuffin/gamemode/sv_core.lua:1: attempt to index global 'LM' (a nil value) 
  1. unknown - gamemodes/lemonmuffin/gamemode/sv_core.lua:1
  2. include - [C]:-1 
  3. unknown - gamemodes/lemonmuffin/gamemode/init.lua:1
  -  person Nick Chris    schedule 28.09.2012

Отговори (2)


arrow_upward
3
arrow_downward

вие пишете: за размяна на време за пресичане на пространство на кратни на (някои) композити също, [...] O(1) пространство с O(N * log N) време. как? бихте ли предоставили някои насоки/връзки, моля? Да се ​​съхраняват начални точки за всеки коефициент не би било O(1) място и да се преизчислят началните точки за всеки сегмент, за къси сегменти неизбежно ще се влоши до пробно разделяне, нали? И всеки сегмент с фиксиран размер в крайна сметка ще стане къс. Дървовидното сливане на кратни на коефициентите е N*log N, но неявната му граница не е O(1). Моля обяснете?
person ajon    schedule 28.09.2012
comment
IMHO, първият параграф дава пълен отговор. Останалото просто го замъглява. - person jplot; 28.09.2012

arrow_upward
0
arrow_downward

стъпки:

  1. Сортирайте трите списъка с помощта на O(N lgN) алгоритъм за сортиране.
  2. Извадете един елемент от всеки списък.
  3. Ако някой от списъците, от които сте се опитали да изскочите, е празен, тогава сте готови, т.е. не съществува общ елемент.
  4. В противен случай сравнете трите елемента.
  5. Ако елементите са равни, сте готови - намерили сте общия елемент.
  6. В противен случай запазете максимума от трите елемента (постоянно време) и попълнете от същите списъци, от които двата елемента са били изхвърлени.
  7. Отидете на стъпка 3.

Стъпка 1 отнема O(N lgN), а останалите стъпки отнемат O(N), така че общата сложност е O(N lgN).

person user650654    schedule 29.09.2012