Exactly. Thanks.
On Nov 8, 7:02 pm, yq Zhang wrote:
> Vikas,
>
> The cost of removing elements from the matrix is O(N) it self. So by
> removing N^2/2 elements, the complexity of your algo should be N^3. However
> there are well-known algo for median in O(N) time in this case O(N^2)
> *because t
I think he means the K-Median selection algorithm (which is what
Hopcroft et al call it). This is O(n), where n is the number of
elements, but here n = N^2. We can do better than O(N^2) as we have
discussed.
On Nov 8, 4:00 pm, Anup Ghatage wrote:
> I googled around and couldn't find a good sou
Vikas,
The cost of removing elements from the matrix is O(N) it self. So by
removing N^2/2 elements, the complexity of your algo should be N^3. However
there are well-known algo for median in O(N) time in this case O(N^2)
*because there are N^2 elements.
On Tue, Nov 8, 2011 at 6:58 AM, vikas
I googled around and couldn't find a good source for the K-Median Theorem.
So, could you provide a good link?
On Tue, Nov 8, 2011 at 2:55 PM, sagar sindwani wrote:
> Use K-Median theorem with k=N
>
>
> On Mon, Nov 7, 2011 at 11:33 PM, Gene wrote:
>
>> Can you explain how a heap helps get the ans
Gene,
we are not creating heap here but using the sorted matrix as heap
itself.
so use same logic of removing items from heap , in this case you have
either right/bottom to reconstruct the structure. removing N^2 /2
items will give you the median.
On Nov 7, 11:03 pm, Gene wrote:
> Can you explain
Use K-Median theorem with k=N
On Mon, Nov 7, 2011 at 11:33 PM, Gene wrote:
> Can you explain how a heap helps get the answer? Just to put the
> elements in a heap requires O ( N^2 log (N) ) time.
>
> On Nov 7, 4:12 pm, vikas wrote:
> > I think the best we can have is nlogn solution with the he
Can you explain how a heap helps get the answer? Just to put the
elements in a heap requires O ( N^2 log (N) ) time.
On Nov 7, 4:12 pm, vikas wrote:
> I think the best we can have is nlogn solution with the heap approach.
>
> On Nov 6, 10:27 pm, Dave wrote:
>
>
>
> > @Mohit: Here is a counterex
I think the best we can have is nlogn solution with the heap approach.
On Nov 6, 10:27 pm, Dave wrote:
> @Mohit: Here is a counterexample:
>
> 10 11 52 53 54
> 20 21 112 113 114
> 30 31 122 123 124
> 40 41 132 133 134
>
Sorry I did not realize you meant the anti-diagonal. Dave gave a good
example where the anti-diagonal also does not contain the median.
If you go back to the partitions I described, you can "force" the
median to be any element that appears just right or below a partition
with 1+floor(N^2) elements
@Mohit: Here is a counterexample:
10 1152 53 54
20 21 112 113 114
30 31 122 123 124
40 41 132 133 134
50 91 142 143 144
The median is 91, and it is not on the anti-diagonal.
Dave
On Nov 6, 3:11 am, mo
It's the wrong diagonal and that algo still holds until another example. btw I
think if the median of the sorted matrix is the median of the second diagonal
then you have found a stable algorithm to find the median of any array by
sorting rows and columns in O(2 sqrt N * sqrt N * log sqrt N) = O
@Gene
As i said in my earlier post right to left diagonal partitions the martix
into 2 equal number of elements. So now the median must be in this
diagonal. Now our focus is on finding median of this diagonal only.
I think this works fine. Can u give some test case for which it fails?
On Sun, Nov
Unfortunately this isn't true. See the example I gave earlier:
1 2 3
2 4 5
3 4 6
Thje median is 3.
1 2 2 3 >3< 4 4 5 6
Niether one of the 3's lies on the diagonal.
When you pick any element P on the diagonal, all you know is that
anything to the right and downward is no less than P and everyth
I think this can be done in O(n) time simply by finding the median of
elements at DIAGNOL starting from right corner to left corner.
Coz as elements are sorted row-wise and column-wise , it implies that
elements below this diagonal are all greater than elements on this diagonal
and all above this a
Hi,
I think the median will always lie on the diagonal
a[n][1] a[1][n]
because the elements on the LHS making the upper triangle will
always be less than or equal to the elements on the diagonal
and the RHS, elements in the lower triangle will be greater than or
equal to them.
so sort the di
Here's an idea. Say we pick any element P in the 2D array A and use
it to fill in an N element array X as follows.
j = N;
for i = 1 to N do
while A(i, j) > P do
j = j - 1;
end;
X(i) = j;
end;
This algorithm needs O(N) time.
The elements of X split each row with respect to P. That is,
any better solution than O(N^2) in worst case?
How do we take advantage of sorting and find in O(N lg N)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/UdC
Try
1 2 3
2 4 5
3 4 6
1 2 2 3 >3< 4 4 5 6
Median 3, median of medians is 4.
On Nov 2, 11:33 am, Anup Ghatage wrote:
> Median of Medians?
>
> On Tue, Nov 1, 2011 at 10:44 PM, Ankuj Gupta wrote:
> > We have a N X N matrix whose rows and columns are in sorted order. How
> > efficiently can we fi
I was thinking on the lines of heap
On Nov 2, 8:33 pm, Anup Ghatage wrote:
> Median of Medians?
>
> On Tue, Nov 1, 2011 at 10:44 PM, Ankuj Gupta wrote:
> > We have a N X N matrix whose rows and columns are in sorted order. How
> > efficiently can we find
> > the median of those N^2 keys ?
>
> >
19 matches
Mail list logo
