On 12 April 2010 23:57, souri datta souri.isthe...@gmail.com wrote:
Why only median of median?
@Souri: It's because using order statistics (randomized select) , you have
an expected time complexity of theta(n) .
But the upper bound is n^2 even to find the smallest element. So to ensure
Hey rohit.You were referring to Binary tree.Search keyword was
missing.Because rotation makes no sense in binary tree.Please note binary
tree and BST are different.
On Mon, Apr 12, 2010 at 12:33 PM, Rohit Saraf
rohit.kumar.sa...@gmail.comwrote:
Read the slides i uploaded. They explain what
are yaar... i meant BST... i thought that was obvious !
sry if i confused you
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Mon, Apr 12, 2010 at 12:38
On Mon, Apr 12, 2010 at 12:58 PM, Rohit Saraf
rohit.kumar.sa...@gmail.comwrote:
are yaar... i meant BST... i thought that was obvious !
sry if i confused you
@rohit It's ok.Actually in this group people come up with very different and
non-common solutions so its risky to take things
I have already given an O(n) solution. See above !
The BST solution is O(nlogn) but is practically more nice. :)
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
Steps:
1. Find the kth element using order statistics - O(n)
2. In one pass over the array, get all the elems less than the kth element.
Let me know if this is not correct.
On Mon, Apr 12, 2010 at 1:57 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
I have already given an O(n) solution.
Find the kth element using order statistics - O(n)As far as i know , u
will have to use median of medians selection algorithm for this...
Rest is fine..
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT
Oh yes.Median of medians selection algo is with the best complexity O(n).
anythin else?
On Mon, Apr 12, 2010 at 7:51 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
Find the kth element using order statistics - O(n)As far as i know ,
u will have to use median of medians selection
On 11 April 2010 10:46, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
Construct a binary tree from the data (maintain the size of subtree under
each node).
Do rotations till the left subtree does not have size k. Rotation is a
constant time operation.
Please prove the correctness of your
Time complexity is O(n log n). But the last solution I gave has O(n).
What did u not understand abt thesolution
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Sun, Apr 11, 2010 at 9:56 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
Time complexity is O(n log n). But the last solution I gave has O(n).
What did u not understand abt thesolution
@Rohit Please explain how that Binary tree solution works.
On 11 April 2010 21:56, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
Time complexity is O(n log n). But the last solution I gave has O(n).
What did u not understand abt the solution
Median of medians is a decent algorithm for extracting the kth element( an
element of kth rank ).
I
On 11 April 2010 11:06, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
I realised now that it can be done easily as :
we can find the kth largest element in O(n) using Linear general
selection algorithm - Median of Medians algorithm
Well , can we do better than O(n log n ) in creating a BST
once u get kth element , u can find first k by a linear travel through the array
On 4/11/10, Priyanka Chatterjee dona.1...@gmail.com wrote:
On 11 April 2010 11:06, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
I realised now that it can be done easily as :
we can find the kth largest
but still the binary tree solution is of more practical use.i will
explain the solution once i reach my comp
On 4/11/10, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote:
On Sun, Apr 11, 2010 at 9:56 PM, Rohit Saraf rohit.kumar.sa...@gmail.com
wrote:
Time complexity is O(n log n). But the
Construct a binary tree from the data (maintain the size of subtree under
each node).
Do rotations till the left subtree does not have size k. Rotation is a
constant time operation.
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science
I realised now that it can be done easily as :
we can find the kth largest element in O(n) using Linear general selection
algorithm - Median of Medians algorithm
Well , can we do better than O(n log n ) in creating a BST from an array of
size n ?
nice solution appreciate it. but your algorithm is wasting time in finding
all the element...
instead of that just find boundary line kth element which can help as in
finding element greater that kth and element small than kth and that soluton
can be done in O(N)
On Sun, Mar 28, 2010 at 10:02 PM,
Design the most efficient algorithm to find the first k smallest elements
in an array ?
--
Thanks Regards,
Priyanka Chatterjee
Third Year Undergraduate Student,
Computer Science Engineering,
National Institute Of Technology,Durgapur
India
http://priyanka-nit.blogspot.com/
--
You received
i feel heapify the array to get a min heap and keep extracting root k
times.any further optimisations???
On Sun, Mar 28, 2010 at 11:33 AM, Priyanka Chatterjee
dona.1...@gmail.comwrote:
Design the most efficient algorithm to find the first k smallest elements
in an array ?
--
Thanks
There are about 5-6 solutions mentioned at
http://geeksforgeeks.org/forum/topic/kth-largest-element
anyone having a different and more efficient algorithm please come up.
On Sun, Mar 28, 2010 at 11:44 AM, sharad kumar aryansmit3...@gmail.comwrote:
i feel heapify the array to get a min heap and
On 28 March 2010 11:44, sharad kumar aryansmit3...@gmail.com wrote:
i feel heapify the array to get a min heap and keep extracting root k
times.any further optimisations???
This algorithm works in O(n+k logn) time. It is good .
Can this be done using randomized selection algorithm in linear
hi, refer cormen book *Medians and Order Statistics* chapter .
On Sat, Mar 27, 2010 at 11:14 PM, sharad kumar aryansmit3...@gmail.comwrote:
i feel heapify the array to get a min heap and keep extracting root k
times.any further optimisations???
On Sun, Mar 28, 2010 at 11:33 AM, Priyanka
select algorithm in order statistics given in cormen book. get kth smallest
element in O(n) and output all array elements from index 0 to the index of
that kth smallest element. So better than Heap approach which is O(n+klogn)
Thanks regards,
Laxmikant Agrawal
Journey is more important than
Create a temp array temp[0..k-1] of size k.
2) Traverse the array arr[k..n-1]. While traversing, keep updating the
smallest element of temp[]
3) Return the smallest of temp[]
Time Complexity: O((n-k)*k).
try it ..for this problem[?]
--
You received this message because you are
you have to find the kth element of your list. which will take O(n)
and remaining element you can get in the other traversal
eg: 3,5,4,35,599,34
you have to find the 3 min element from the lsit
so finding 3rd element we will get 5
on next thing is traverse the list and take all the element less
1) Construct max heap by taking first k elements in an array
2) if k+1 element less than root of max heap
a) Delete root of max heap
b) Insert k+1 element in max heap and apply heapify method
3) else skip the element
4) apply above procedure for all n elements in an array
At last
27 matches
Mail list logo
