c++ - 在数组中创建位置层次结构

Question

我有以下任务。我们得到一个 N 大小的数字和一个以适用于该算法的方式填充整数的数组。现在我们数组中的每个数字基本上都是数组中的一个位置。每个阵列都有一个领导者。它是与它在数组中的位置具有相同值的点。一个示例数组是:

1 2 4 5 4 1

在这个数组中，领导者的值为 4，因为它位于第 4 个位置。在我们获得的数据中，必须始终有一个领导者。现在我们制作一个层次结构。领导者获得值 0，指向他的那些值，因此在这种情况下值为 4 获得新值 1，依此类推。为了形象化，上面的数组变为:

3 2 1 4 0 3

Leader 是 0，在位置 2 我们也有一个 4 所以它成为层次结构中编号为 1 的下一个。在位置 1 我们有一个 2 所以它指向第二个位置 - 层次结构中的新 1 所以它成为层次结构中的第二个，依此类推。原始数组中每隔一个 2 也会变成一个 2。

输入数据将以txt文件形式给出。现在我需要最好的算法来完成这项工作。我用递归做了一个。这里我也想问一下复杂度是多少。是不是N*logN？输入来自一个文件，N也是。示例输入file.txt是
4
1 2 3 3
6
1 2 4 5 4 1

上面的输出(稍后):
3 2 1 0
3 2 1 4 0 3

这是我的代码(输入暂时固定):

#include <iostream>
using namespace std;

int *T;

int nr(int x)
{
if (T[x] == x)
    return 0;
else
    return nr(T[x]) + 1;
}

int main()
{
    int n, m, leader;

    n = 6;
    T = new int[n];
    int T1[6];

    T[0] = 1;
    T[1] = 2;
    T[2] = 4;
    T[3] = 5;
    T[4] = 4;
    T[5] = 1;

    for (int i = 0; i < n; ++i)
    {   
        T1[i] = nr(i);  
    }

    for (int i = 0; i < n; ++i)
    {
        cout<<T1[i]<<" ";
    }
    cout << endl;

    delete[] T;
}

Answer 1

对于每个位置，我们想知道哪些单元格指向它。

1 2 4 5 4 1

5: 3
4: 2, 4 (leader)
3: None
2: 1
1: 0, 5
0: None

现在跟随领导者向后:

Who's looking at 4?
  -> 2
[x, x, 1, x, 0, x]

Who's looking at 2?
  -> 1
[x, 2, 1, x, 0, x]

Who's looking at 1?
  -> 0 and 5
[3, 2, 1, x, 0, 3]

Who's looking at 0 or 5?
  -> 3
[3, 2, 1, 4, 0, 3]

伪代码:

// For each position, we'd like to know
// which cells are pointing to it
A = input array
leader = None
map = {}

for i=0 to length(A)-1:
  if i = A[i]:
    leader = i

  if i != leader:
    if A[i] in map:
      map[A[i]].append(i)
    else:
      map[A[i]] = [i]


//Now follow backwards from the leader
output = Array(length(A))
next = leader
output[leader] = 0
rank = 0

// Assumes the data provides
// for a straightforward solution.
// There may be edge cases to work
// out if that's not the case.
while next:
  for i in map[next]:
    next = None
    if i in map:
      next = i
      rank = rank + 1
      for j in map[next]:
        output[j] = rank
      break