kabirdutt0907's blog

By kabirdutt0907, history, 7 weeks ago, In English

Yesterday I came across a question whereby I need to store the location and the respective element at that location and every time I need to access the location to perform the given operation here the array elements can repeat I know for some of you the doubt may be silly But i am kinda weak in data structure So please help..

 
 
 
 
  • Vote: I like it
  • -18
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

use vector pair for storing same element and its index.(means we are using vector pair as map) vector<pair<ll,ll>>v; here ll is long long int

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    but i need to access the element as v[element] to get the location ?

»
7 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

You can use a map of vectors in this case, like map<int, vector<int>> idx where key will be the element itself and the value will be its indices. Alternatively, you can also use something like map<int, set<int>> idx to perform .count() or other set operations efficiently.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

you can write v.push_back(make_pair(a[i],i)).for accessing element u you simply write v[i].first and for index v[i].second.I hope this will work

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's take a specific problem as an example. Say you're given a list of ints 43, 24, 11, 35, 52 and you want to print the indices of where the original elements go after the list gets sorted. So it would be 4 2 1 3 5 in this case.

What you'd do is store it in a vector<pair<int, int>> arr, where arr[i].first is the value at position i, and arr[i].second is the index (i originally, but will change after sorting).

Then sort the array and print out all arr[i].second values.

Another similar use is for permutations. It's often necessary to 'invert' them (not sure if that's correct terminology). So if you have an array perm[i], you want another array ind[i] such that perm[ind[i]] = i (ind[i] stores the index of i in perm). What you do is iterate through perm and set ind[perm[i]] = i for all 0 <= i < n.