🚀 go-pugleaf

Jack D wrote on 05-12-2002 15:21:

> Toni Van Remortel wrote on 03-12-2002 09:30:
> 
>> keanu wrote:
>> 
>>> <knip>
>>> 
>>> waar zit de vraag ? :)
>> 
>> <quote>
>> Ik heb wel een idee hoe ik het kan oplossen, maar ik had graag ook nog een
>> andere kijk op het probleem gehad.
>> </quote>
>> 
>> OK, er staat geen ? tussen, maar ik had gehoopt dat er topch slimme mensen
>> tussen zaten ;-)
>> Onderwijl ga ik mijn eigen oplossing gebruiken (gewoon een lusje waain elk
>> voorkomen wordt geteld. kan ik nadien ook nog een % weergeven).
> 
> Als er een bovengrens zit op de getallen die je wilt gebruiken, kan je per
> array en bitmask opstellen van de (al dan niet) voorkomende waardes. Als je
> dan een bitwise & van de vier waardes doet, krijg je een bitmask waarin alle
> waardes die steeds voorkomen op 1 staan.
> 
> Als er geen voorkomt, zal je de verschillende combinaties van n-1 array
> moeten combineren met elkaar etc. Deze methode zal zeker sneller zijn als de
> lengte van de arrays groter is dan het aantal arrays.
> 
> Een andere mogelijke optimalisatie die ik zie, is om hetgeen te doen dat jij
> zegt, maar niet in arbitraire volgorde, ik zou beginnen met de elementen uit
> de kortste array. Als deze al overal voorkomen, ben je er, zoniet, dan pak
> je er de elementen uit de tweede kortste bij en tel je deze elementen ook,
> als er dan elementen n-1 keer voorkomen (n = aantal arrays) is dit de
> oplossing en zo verder.
> 
> Hopelijk helpt dit een beetje,
> Greetz,
> Jacko

Beuh, heb nog even zitten denken en de eerste methode heeft weinig zin, het
is interessant als je de data nog wil bijhouden om nog allerlei toestanden
mee uit te rekenenen, maar voor dit specifiek probleem is de complexiteit
van het opstellen van de bitmasks gelijk aan het tellen van alle elementen.

De tweede methode heeft wel zin (kwestie dannek toch nog iets deftig
geproduceerd heb ook :) ) op voorwaarde dat de arrays gesorteerd zijn.