kabirdutt0907's blog

Is there any way to store the location of an array element and that array element were the array elements can be repeated

By kabirdutt0907, history, 5 years 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

Comments Comments (1)
| Write comment?
»
5 years ago, hide # |
 
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.

→ Reply