3 Replies - 631 Views - Last Post: 04 August 2013 - 10:41 AM Rate Topic: -----

#1 TamimAddari  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 28-February 13

How find the highest number of frequency in a range of number?

Posted 04 August 2013 - 12:47 AM

I am given a range of numbers in a non-descending order. Now in the query I have find the frequency number of the highest frequency. I tried to build a segment tree of the maximum frequencies. but I am having problem writing the query program. Here's my code
 
    #include <iostream>
    #include <map>
    using namespace std;
    int left(int p) { return p<<1; }
    int right(int p) { return (p<<1)+1; }
    int parent(int p) { return p>>1; }
    void buildTree(int *A,int *st,int p,int L,int R,map<int,pair<int,int> > &strtEnd)
    {
    	if(L==R)
    		st[p]=1;
    	else
    	{
    		buildTree(A,st,left(p),L,(L+R)/2,strtEnd);
    		buildTree(A,st,right(p),(L+R)/2+1,R,strtEnd);
    		if(A[(L+R)/2]==A[(L+R)/2+1])
    		{
    			int cnt = strtEnd[A[(L+R)/2]].second-strtEnd[A[(L+R)/2]].first+1; 
    			st[p] = max(max(st[left(p)],st[right(p)]),cnt);	
    		
    		}
    		else
    			st[p] = max(st[left(p)],st[right(p)]);
    	}
    }
    int query(int *A,int *st,int p,int L,int R,int i,int j)
    {
    	if(R<i||L>j) return -1;
    	if(L>=i&&j>=R) return st[p];
        // now what??
    	
    
    }
    
    int main()
    {
      
    	int n;
    	int A[n];
    	map<int,pair<int,int> > first_last;
    	for(int i = 0;i<n;++i)
    		{
    			cin>>A[i];
    			if(i==0)
    				first_last[A[i]].first = i;
    			else if(i==n-1)
    				first_last[A[i]].second = i;
    			 else if(A[i]!=A[i-1])
    				{
    					first_last[A[i-1]].second = i-1;
    					first_last[A[i]].first = i;
    				
    				}
    			
    		}
    	int st[4*n+2];
    	buildTree(A,st,1,0,n-1,first_last);
    	int queries;
    	cin>>queries;
    	while(queries--)
    	{
    		int i,j;
    		cin>>i>>j;
    		cout<<query(A,st,1,0,n-1,i,j);
    	
    	
    	}
    
    
    }



I am really having trouble designing the query program.I am also having segmentation fault with my buiild function. :(/>

Is This A Good Question/Topic? 0
  • +

Replies To: How find the highest number of frequency in a range of number?

#2 Michael26  Icon User is offline

  • DIC-head, major DIC-head
  • member icon

Reputation: 362
  • View blog
  • Posts: 1,534
  • Joined: 08-April 09

Re: How find the highest number of frequency in a range of number?

Posted 04 August 2013 - 05:29 AM

Can't you use Hashtable, for each element in the array, do like counts[element] = counts[element] + 1 .
When you are done, loop through the map and find the max.
Was This Post Helpful? 0
  • +
  • -

#3 TamimAddari  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 28-February 13

Re: How find the highest number of frequency in a range of number?

Posted 04 August 2013 - 07:05 AM

View PostMichael26, on 04 August 2013 - 05:29 AM, said:

Can't you use Hashtable, for each element in the array, do like counts[element] = counts[element] + 1 .
When you are done, loop through the map and find the max.

There numbers range from -100000 to 100000.There is negative numbers. So, hashing doesn't seems possible..
Was This Post Helpful? 0
  • +
  • -

#4 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3630
  • View blog
  • Posts: 11,325
  • Joined: 05-May 12

Re: How find the highest number of frequency in a range of number?

Posted 04 August 2013 - 10:41 AM

Hashing will work as long as you use a suitable hash function that maps negative numbers to appropriate slots in the hash table.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1