0

Let's say I have an array of N elements, each element representing a unique integer between 0 and N-1. Let's say I want to find the index of a given integer, I can loop through the array and return the index when I find the number. Since this is inefficient, I could make a second array, so that for first_array[10] = 55 we'd obtain second_array[55] = 10.

Now let's say that I don't want to create a second array and I want to do the switch in-place. Is there a clever way to do this, clever meaning no extra allocation, no crazy deep recursion and no searching through the whole array N times? Does this kind of operation have a name? I feel like this is a problem that must have already been solved but I can't imagine what it could be called.

Edit: This is a question about an algorithm, the answer, being an algorithm, should work the same regardless of the programming language.

Michel Rouzic
  • 1,013
  • 1
  • 9
  • 22
  • in which Language ? – gsharew Jun 18 '22 at 11:51
  • Any language, the language doesn't really matter here since it's about an algorithm, but I'll implement the answer in C. – Michel Rouzic Jun 18 '22 at 11:54
  • Ok if it is any language ? why don't you use built in API like arrayName.indexOf().... – gsharew Jun 18 '22 at 11:56
  • but if it is algorithm matter it would be using c or c++. anyways i can think of the solution for that problem – gsharew Jun 18 '22 at 11:57
  • What “switch“ do you want to do? You have described a second array that maps from values to indices but said you do not want to create that array. What two things do you want to switch? Do you want to transform the first array so that it becomes the described second array? – Eric Postpischil Jun 18 '22 at 12:39
  • Yes, I want to transform the first array so that it becomes like the second array. – Michel Rouzic Jun 18 '22 at 12:44
  • 1
    The array effectively encodes a permutation, making this question a duplicate of [this one](https://stackoverflow.com/questions/56603153/how-to-invert-a-permutation-represented-by-an-array-in-place). [This answer](https://stackoverflow.com/a/66807322/298225) refers to [this paper](https://arxiv.org/pdf/1901.01926.pdf). – Eric Postpischil Jun 18 '22 at 12:49

1 Answers1

0

if the question is about javascript, you can simply use indexOf() method. in your case:

first_array.indexOf(55); // it will return index of **55** in first_array
Abdul Basit
  • 9
  • 2
  • the OP needs C language. – gsharew Jun 18 '22 at 11:58
  • When I asked without specifying a language I didn't think that people would assume the language and give language-specific answers (even if the question was JavaScript this wouldn't even be a suitable answer given that I asked about transforming the array). I'm asking for a general algorithm. – Michel Rouzic Jun 18 '22 at 12:00
  • @MichelRouzic as long as your question is related with searching the efficient way to do that would be sort them and use binray search. – gsharew Jun 18 '22 at 12:05
  • No the problem isn't really about searching. See if you do the transformation out-of-place, you can do it sequentially with no searching involved by doing something like `second_array[first_array[i]] = i;`. The problem is with doing it in-place. – Michel Rouzic Jun 18 '22 at 12:08
  • if the problem is not about searching, and we are doing everything in place, without using a new array; then what exactly is your question. It would be great if you could kindly elaborate. like @gsharew said, we can do sorting then binary search, specifically in-place merge sorting to avoid new array creation, or any other in-place sorting – Abdul Basit Jun 18 '22 at 12:17
  • The question is how do I transform an array like `{ 4, 0, 2, 1, 3 }` into `{ 1, 3, 2, 4, 0 }` in-place, the second array containing the indices at which the values of the first array are the indices in the second array. – Michel Rouzic Jun 18 '22 at 12:22
  • I got it now, so searching wasn't needed at all, what you are looking for is to transform the array so you want in-place swapping without knowing the index of the element, to be more precise? – Abdul Basit Jun 18 '22 at 12:45