This is part of a larger program, but this is the bottleneck.

Given an array of numbers that mean "repeatedly splice the element at this index out of an array", I want to generate an array that represents the order in which each element should be spliced.

So the following:

[3, 1, 4, 4, 3, 1, 1]

means to run these operations:

[a, b, c, d, e, f, g]
[a, b, d, e, f, g]    // 3rd element removed, c
[b, d, e, f, g]       // 1st element removed, a
[b, d, e, g]          // 4th element removed, f
[b, d, e]             // 4th element removed, g
[b, d]                // 3rd element removed, e
[d]                   // 1st element removed, b
[]                    // 1st element removed, d

And I want to generate (without actually running all of the splice operations above):

[2, 6, 1, 7, 5, 3, 4]

which is the order in which each element was removed.

Looking for a solution better than O(N^2)

Below is not part of the question, just what I'm actually doing, for anyone interested:

This is part of a seam carving implementation. I'm generating a compressed format that represents all of the seams in a given image, and then removing those seams in the client. Since a seam always moves 1px left or right at each step, a seam can efficiently be stored as:

starting index, left, right, left, left, left, right, ...

I then remove this seam from the image, and calculate the next one. Storage wise it's 2 bytes 1 bit per pixel after that, or a seam of length 1024 is stored in 130 bytes.

With respect to the original indicies, however, "left 1" and "right 1" is only accurate for the first seam. After that any seam can cross over another seam, so "right 1", with respect to the original indicies, could mean move right 10, or even move left 10.

In other words I'm just trying to decompress this data.

CodePudding user response：

The simplest O(N log N)-time implementation would probably be with a Fenwick tree. C implementation below.

#include <iostream>
#include <vector>

int NextPowerOfTwo(int n) {
  n |= n >> 1;
  n |= n >> 2;
  n |= n >> 4;
  n |= n >> 8;
  return n   1;
}

class FenwickTree {
 public:
  explicit FenwickTree(const int n) : sums_(NextPowerOfTwo(n)) {}

  void Add(int index, const int delta) {
    while (index < sums_.size()) {
      sums_[index]  = delta;
      index  = index & -index;
    }
  }

  int RankQuery(int target) const {
    int index = 0;
    for (int stride = sums_.size() >> 1; stride > 0; stride >>= 1) {
      if (sums_[index   stride] < target) {
        target -= sums_[index   stride];
        index  = stride;
      }
    }
    return index   1;
  }

 private:
  std::vector<int> sums_;
};

std::vector<int> Decompress(const std::vector<int>& splice_indices) {
  const int n = splice_indices.size();
  FenwickTree tree(n);
  for (int i = 1; i <= n; i  ) tree.Add(i, 1);
  std::vector<int> result(n);
  for (int i = 1; i <= n; i  ) {
    const int j = tree.RankQuery(splice_indices[i - 1]);
    tree.Add(j, -1);
    result[j - 1] = i;
  }
  return result;
}

int main() {
  for (int i : Decompress({3, 1, 4, 4, 3, 1, 1})) std::cout << ' ' << i;
  std::cout << '\n';
}

CodePudding user response：

make 2 new arrays. Index_old is the same size as your original array, and number it consecutively index_new starts out empty. loop through your array with numbers, removing that element from index_old and adding it to the end of index_new

index_old[1,2,3,4,5,6,7]
index_new[]

//3rd element removed
index_old[1,2,4,5,6,7]
index_new[3]

//1st element removed
index_old[2,4,5,6,7]
index_new[3,1]

//4th element removed
index_old[2,4,5,7]
index_new[3,1,6]

//4th element removed
index_old[2,4,5]
index_new[3,1,6,7]

//3rd element removed
index_old[2,4]
index_new[3,1,6,7,5]

//1st element removed
index_old[4]
index_new[3,1,6,7,5,2]

//1st element removed
index_old[]
index_new[3,1,6,7,5,2,4]

then create an index final array of the same size and loop

for i= 1 to 7
  final[index_new[i]] = i

as it iterates, the loop will populate the final like this

[0,0,0,0,0,0,0]
[0,0,1,0,0,0,0]
[2,0,1,0,0,0,0]
[2,0,1,0,0,3,0]
[2,0,1,0,0,3,4]
[2,0,1,0,5,3,4]
[2,6,1,0,5,3,4]
[2,6,1,7,5,3,4]