In the general case, we can reduce Element-Distinctness(ED) problem to
this problem. Since ED has a lower bound of Omega(n log n), we cannot
get an O(n) algorithm for this problem.
http://en.wikipedia.org/wiki/Element_distinctness_problem
-Jagadish
http://www.cse.iitb.ac.in/~jagadish
On Jun 2
>Why not just change the definition of when one number is bigger than another
>and do normal sort ?
>I guess that is better and simpler.
Normal sort takes O(n log n), while Anurag's algo is O(n).
Regards,
Jagadish
http://www.cse.iitb.ac.in/~jagadish
On Jun 20, 2:18 pm, Rohit Saraf wrote:
> Further to my previous post, one question.
> Can the median be found in O(n) time without using extra memory?
> I am not familiar with the algorithms that find the median though I
> know the
> median can be found in O(n) time.
>
This is important! I don't see how the standard algorithm for media
> 3) Whenever a number repeats instead of storing the count store modify the
> number to (number + ROOT Value) ie for 2 which is repeated twice 2 + 3 +3 =
> 8 instead of 2:3 as you give in your example.
>
> 4) Since in a heap no number can be greater than root value whenever a
> number greater tha
:23:2
and so on...
Since, there are only k distinct keys the heap size will at most be k;
so each search/insert/increment operation takes O(log k) time.
Jagadish
http://www.cse.iitb.ac.in/~jagadish
>
> On 2010-5-17 22:38, Jagadish M wrote:
>
>
>
> > The best algorithm
On May 17, 5:36 pm, Rohit Saraf wrote:
> @divya : descending order sorting works. BRILLIANT !!
Not really.
Try this input: 8 6 5 5 5 1
The best partition is [8 6 1] [5 5 5] but Divya's algorithm gives [8
5 1] [6 5 5].
-Jagadish
http://www.cse.iitb.ac.in/~jagadish
> On 5/17/10, divya
The best algorithm I can think of is to maintain a heap of k elements.
Takes O(n log k) time.
Is anything told about the values of the keys? If the keys have values
less than N, then it is possible to do
what you say, i.e sort them in place.
-Jagadish
http://www.cse.iitb.ac.in/~jagadish
On May
>
> > Try dynamic programming. Complexity of the algorithm would be O(n^3).
>
Won't it just be O(n^2)?
Suppose A is the input.
Let F(i,+) denote the maximum sum you can accumulate with the sequence
ending at A[i] and the last difference being positive.
Define F(i,-) accordingly. Computing each F
