0
$\begingroup$

Ok, so I got this for homework and been struggling for a while now. The full assignment requires this:

While N = number of elements in given array and n = number of different elements,

init(S,A[1...N]) - accept an array A as input and initialize S data structure in O(Nlogn) time

insert(S,x) - insert the key x to S in $O(\log n)$ time

freq(S,x) - return the number of appearances of x in S, in O(logn) time

mostFreq(S) - return the most frequent element in S, in O(1) time

I was thinking of using a balanced bst, inserting elements from the array one by one, but it would be $O(n \log n)$ and not O(Nlogn) as required.

As for the frequency functions, I was thinking of storing each element with an int attached to it or something, indicating number of appearances so far, thus enabling me to just search for some element to know the number of times he appears in S, but that's messy too.

as for the last function (mostFreq) - I have no idea how to deal with it whatsoever. I guess it involves holding some variable that will be updated on each insert, but I got nothing.

So it's clear I'm pretty lost :) any suggestions?

$\endgroup$
0
$\begingroup$

As for the frequency functions, I was thinking of storing each element with an int attached to it or something, indicating number of appearances so far, thus enabling me to just search for some element to know the number of times he appears in S, but that's messy too.

That's exactly the solution I would go for.

Store a mapping of $\langle x, freq_x\rangle$ in the BST. Because each $x$ will be unique in the bst you will be able to search for the frequency with just $x$.

insert becomes

if x is in BST then
    replace <x, freq> with <x, freq+1> in bst
    if freq+1 > max_freq then
        max_freq := freq+1
        max_x := x
    endif
else 
    insert <x, 1> into bst
    if max_freq = 0 then
        max_freq := 1
        max_x := x
    endif
endif

You don't really need a tree, instead a hashtable would drop the complexity down to O(1) for every access and O(N) for init.

$\endgroup$
  • $\begingroup$ Thx! Nice and smooth :) $\endgroup$ – MatanyaP Jan 11 '18 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.