Storing and displaying numbers the indicies of number that appear 3+times in an array at O(n*logn) o

[perditi0n2002]

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?

an example of the program:
array: 2 3 4 2 2 5 2 4 3 4 2

output:
2: 0,3,4,6,10
4:2,7,9

 

[Willem]

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 ?


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

 

[perditi0n2002]

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 ?

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

No restriction specified, but using a naive bucket sort would
naturally be overkill since it can be any positive integer.

 

[perditi0n2002]

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 ?

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

Any thoughts?

 

[Willem]

perditi0n2002 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