perditi0n2002 wrote:

) On Jan 2, 1:34?am, Willem <(E-Mail Removed)> wrote:

)> perditi0n2002 wrote:

)>

)> ) Hi everyone

)> ) I was given a question that takes a sorted array (well it was unsorted

)> ) but I merge sorted it to simplify the problem) and you must return the

)> ) indicies of numbers which appear 3 or more times in the array, at

)> ) O(n*logn) or less complexity.

)> ) This doesn't seem too plausible to me since even if I were to go over

)> ) the array and make a 2d array of [distinct numbers which appear 3+

)> ) times][n] it would still take me more than n times to go over the

)> ) original array and store the indicies.

)> ) Does anyone have any clue how this is possible?

)>

)> How much extra memory are you allowed to use ?

)

) No restriction specified, but using a naive bucket sort would

) naturally be overkill since it can be any positive integer.

You can store other things besides buckets.

And you only need O(n) extra memory: One thing per original entry.

(Some pedants might point out it's O(n lg n), but that's debatable.)

SaSW, Willem

--

Disclaimer: I am in no way responsible for any of the statements

made in the above text. For all I know I might be

drugged or something..

No I'm not paranoid. You all think I'm paranoid, don't you !

#EOT