Matrix.code's blog

Fast Access in Multiset

By Matrix.code, 10 years ago, In English

I have a multiset . Using a loop I am inserting elements. In each loop , I am asked to access n th element of the multiset . where n is increasing in ascending order,1,2,3,4

I used iterator and pointed it to the begin. But for every loop , I have to iterate . This gives me TLE.

Is there any process for fast accessing in multiset ??

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 7   Vote: I like it -14 Vote: I do not like it

I don't know any function or method to do that, but I have a suggestion for that in O(logM * logM) where M is size of the multiset:
use binary search to find lower_bound of X in interval [minElement,maxElement]. each time check the return value of lower_bound function whether it's distance from begin of multiset equals to N or not.
here is my code.

→ Reply
»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

There is no a efficient way to reach nth element of the multiset. But in your problem we can do it like this :

    multiset<int> Set;
    multiset<int>::iterator ith; // iterator for ith element in multiset
    
    for(int i=1;i<=n;i++){
        cin >> k; // number of elements to insert in this loop
        
        while(k--){
            
            cin >> x; // element to insert
            Set.insert(x);
            
            if( Set.size()==1 ){    // first element inserted 
                ith = Set.begin();
            }
            else if( x <= (*ith) ){ 
                ith--;
            }
        
        }
        
        cout << *ith << endl; //ith element is here
        
        ith++;
    }

I tried this code with several inputs and it worked. Even so sorry for if there is a bug. And notice that in each loop there have to be at least i elements in the multiset to reach ith element :)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I understood... But what will be ? If n is incremented by 1 after 1,2,3,.... insertion 

    for(i=0,n=0,target=1,k=0;i<numOfElements;i++){
    cin>>x;  // input
    Set.insert(x); //inserting in the set
    k++;
    if(target==k) {
       n++; // n is incremented
        //Code for finding nth number in the set
        //
        ///
       k=0;
       target++; // next target
    }

    how would I do fast access ?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      It is easy too.

      multiset<int>::iterator nth;

for(i=0,n=0,target=1,k=0;i<numOfElements;i++){
    cin >> x;  // input
    
    Set.insert(x); //inserting in the set
    if( Set.size()==1 ){ // When the first element inserted, n=0 so 0th element is in the Set.begin()
        nth = Set.begin();
    }
    else if( x <= (*nth) ){ // if x smaller than or equals to nth element we have to decrease nth
        nth--;
    }
    
    k++;
    if(target==k) {
       n++; // n is incremented
       nth++; // When n is incremented, nth have to be incremented too.

       cout << *(nth) << endl; // Do whatever you want with nth element

       k=0;
       target++; // next target
    }
}
      → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      EDT

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    what's the complexity for this code

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      ++ and -- operations on set iterators both have a complexity of O(logN) (N is the number of elements). The total complexity should be NlogN.

      How did you end up reading this 5-year old post btw?

      → Reply