I think hash would be the less space intensive than anything else.
About your example of 1000 elements and big numbers:
Any decent hash function with size 1024 as bucket will give you good results.
Insertion time will be close to O(1)
One such hash would be rotating hash which takes care of all 4 bytes of integer.
unsigned jsw_hash ( void *key, int len )
{
unsigned char *p = key;
unsigned h = 16777551;
int i;
for ( i = 0; i < len; i++ )
h = ( h << 1 | h >> 31 ) ^ tab[p[i]];
return h;
}
Of course, we can find such array whose elements may not get good hash
results and insertion time may increase.
But, for practical purpose and uniform distribution of elements, hash will work.
Let me know your thoughts.
Janak
On Wed, Jun 2, 2010 at 12:03 AM, Veer Sharma <thisisv...@rediffmail.com> wrote:
>
> Hi Janak
>
> Thanks for your reply and good that we are exited. But if you see the
> problem, this approach is already known which has space complexity of
> O(n). But this if you are lucky that the array has numbers which are
> not more than n itself.
>
> If the given array is say 1000 size and it has numbers which can be
> anything, say a very large number 14556543 (lets forget max storage of
> int/long in various programing languages). Then it will be a tough job
> to keep insertion in your hash table O(1). There will be lots of hash
> classes and if you do not chose a good hash function (which can be
> better found by knowing the nature of the numbers in the aray and we
> done know about them) you may end up with O(n) insertion time.
>
> So lets think a less space expensive method.
>
> Tanks,
> Veer
>
> On Jun 1, 9:57 am, janak chandarana <jac...@gmail.com> wrote:
> > On Mon, May 31, 2010 at 10:01 PM, souravsain <souravs...@gmail.com> wrote:
> > > Hi All
> >
> > > This is my first post to this community and so am exited. The problem
> > > is to find the no. that has maximum frequency in an array (size n) of
> > > integers.
> >
> > > The approach to use a hash table, itereate through array (O(n)) and
> > > keep inserting into hash table (O(1)) and then scan the hash table
> > > (O(n)) to find entry with max frequency is known.
> >
> > You don't need to scan hash table again.
> > Keep track of max while inserting.
> > Update max when ever freq of some character is more than max.
> >
> > > Not to mention that
> > > one more iteration is needed to find the maximum value in array so as
> > > to decide the sixe of hash table (to keep insertion perfectly O(N).
> >
> > > I am looking for a solution which is having O(1) space complexity. The
> > > best I can think of is to sort the array in O(nlogn) and then make a
> > > pass through the array O(n) to find one with max frequency. So here
> > > time complexity is O(nlogn + n). Can we have a better solution?
> >
> > > --
> > > You received this message because you are subscribed to the Google Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algoge...@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
