Just got another O(n) solution.
Find the n/2 th largest element in the array using the Median of Medians
Selection algorithm. =? takes O(n)
That's It !
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
Remove as many 3's that would make it 1000.
The example still holds
@gauri: the logic is that if your pivot is greater than all numbers
till middle then it would not effect the middle element. Hence if
middle element is not the mode in the given array, the answerwould be
wrong.
On 4/15/10, vivek
Can we have some mathematical logic behind this. Can we generalise it ?
Regards ,
Gauri
On 4/15/10, Rohit Saraf wrote:
> say u choose the last value as pivot
>
> 1 1 1 1 1 1 1 (499 times) 2 2 2 2 1 1 3 3 3 3 (499 times) 4
>
> 4 is your pivot
> try out
>
> ---
@rohit : thats more than 1000 elements in the array
On Thu, Apr 15, 2010 at 7:48 PM, Rohit Saraf wrote:
> say u choose the last value as pivot
>
> 1 1 1 1 1 1 1 (499 times) 2 2 2 2 1 1 3 3 3 3 (499 times) 4
>
> 4 is your pivot
> try out
>
>
I feel gaurav's solution does it in O(n) time & cons space
but there is a case that when there is no element with n/2+1
appearances the method might fail(eg 1 1 1 2 3 4 and in many other
cases as well...)
but as the problem states that there is atleast 1 element with n/2+1
appearancesthis a
say u choose the last value as pivot
1 1 1 1 1 1 1 (499 times) 2 2 2 2 1 1 3 3 3 3 (499 times) 4
4 is your pivot
try out
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.ii
@rohit : can you give me any counter examples?
PS: one value is occuring >=501 times.
On Thu, Apr 15, 2010 at 5:12 PM, Rohit Saraf wrote:
> It cannot just be partitioned in such a manner that the middle element is
> *always *the mode !
>
> --
> Roh
It cannot just be partitioned in such a manner that the middle element
is *always
*the mode !
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Thu, Apr 15, 2010
Can you illustrate it with an example ?
How are you deciding the pivot for partitioning the array ?
How the middle element can be the mode of the array ?
Regards
Gauri
On Apr 14, 5:39 pm, vivek bijlwan wrote:
> complexity : On)
> extra - memory required : no
>
> have the first iteration of qui
*FINAL SOLUTION* :
I gave a second thought :
A large amount of space(but finite constant and bounded and within practical
limits) will eventually be required for my hashing based solution to be
worst case O(n).
So this problem has an linear time solution..
BUT can we do better in terms of space
10 matches
Mail list logo
