hi all,
nlog(k) is the solution i think.
can anyone suggest more optimal?
solution:
create a min-heap, (condition size should be always k)
temp =0
loop n to a[]
if a[i]temp
if min-heap(root) a[i]
delete root in min- heap
inseart a[i] in min - heap
at the end of main loop the
You must be mistaken in the definition of heaps, or maybe the question,
look at the updated question I put up there.
On Thu, Oct 24, 2013 at 5:48 PM, pankaj joshi joshi10...@gmail.com wrote:
hi all,
nlog(k) is the solution i think.
can anyone suggest more optimal?
solution:
create a
@ Saurabh,
I have done a correction on algo
temp =0
loop n to a[]
if a[i]temp
if min-heap(root) a[i]
if min-heap(count)==k
delete root in min- heap
inseart a[i] in min - heap
As i have made the condition: min-heap, (condition size should be always k)
for this particular
check for {5,2,3} and K = 2.
On Thu, Oct 24, 2013 at 7:41 PM, pankaj joshi joshi10...@gmail.com wrote:
@ Saurabh,
I have done a correction on algo
temp =0
loop n to a[]
if a[i]temp
if min-heap(root) a[i]
if min-heap(count)==k
delete root in min- heap
inseart
@pankaj : how can you maintain increasing sub-sequence using
heapyour soln is for finding finding K largest element in the
array...so it wont work.
On 10/24/13, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote:
check for {5,2,3} and K = 2.
On Thu, Oct 24, 2013 at 7:41 PM, pankaj joshi
@Saurabh:
As per the question the elements of sub-sequence should be increasing,
so the solution will be {5} and as per the program.
* but as written longest sub-sequence of k =2, so it should be {2,3} for
this case. (there should be backtrack in this case.)
@atul: increasing sub sequence is
in your updated algo , you should be using max-heap not min-heap.
check your algo for :-
1,2,5,10,100,30,8,555
let me know if it work fine.If it is working fine then i need more
clarity of your algo
On 10/24/13, pankaj joshi joshi10...@gmail.com wrote:
@Saurabh:
As per the question the
Max-heap should not used in this case,
why min heap? -- this is because program has to decide the smallest element
in k-group.
in your example if i consider k =3 than
insert 1
insert 2
insert 5
insert 10
size of heap ==4 so delete root of min- heap (which is 1),
insert 100
30 cant insert because
OK, i got now why you were using min-heap.
now consider this example :-
200,12,33,1,55,100
K=3
insert 200
12 200...cannot insert
33 200...cannot insert
.
.
.
100200 cannot insert
output : 200 (not lenght of k)
output should be : 33,55,100
On 10/24/13, pankaj joshi joshi10...@gmail.com