c++ - 如何在一个未排序数组中找到另一个数组元素的不同索引？

Question

有2个字符数组。两个数组大小相同，形式互为混杂。

例如:

char a[] = {'a', 'b', 'a', 'b', 'c', 'a', 'b', 'a', 'b', 'c' };
char b[] = {'a', 'a', 'b', 'b', 'c', 'c', 'b', 'b', 'a', 'a' };

我想在数组a中找到数组b的元素的不同位置(基于1的索引)，即:1、3、2、4， 5、10、7、9、6、8，对于这个例子。

我实现了以下O(n²) 的蛮力方法:

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        if (b[i] == a[j])
        {
            cout << j + 1 << " ";
            a[j] = '\0';
            break;
        }
    }
}

在 C++ 中是否有任何方法可以将时间复杂度降低到类似 O(n * log(n))甚至更少？

Answer 1

它可以以 O(n) 的内存为代价减少到 O(n) 的时间。

您应该创建二维数组。它的第一个维度将由所有字符组成(总共 256=2^8 个索引，因为 sizeof(char)=1 字节)，第二个维度将超过数组的 n 个元素。

所以，如果你有

char a[n] = ...;
char b[n] = ...;

你应该分配

int c[256][n]; // O(n) memory
int s[256]; // O(1) memory
int e[256]; // O(1) memory

并用零填充它们。您将能够使用 e[i] 作为 a 中代码为 i 的字符数的计数器。在 c[i][0]、c[i][1]、...中，您可以将代码 i 中字符的实际位置存储在数组 a 中。

第一步是遍历数组a，每次

1. 将字符的位置写入c[a[i]][m] = i，其中m = e[a[i]]
2. 增加e[a[i]]

您可以使用数组s 来存储符号已打印位置的数量(s[j] 是代码为j 的打印字符数)。第二步是遍历 b 并且每次

1. 输出 c[b[i]][m]，其中 m = s[b[i]]
2. 增加 s[b[i]]

每一步消耗O(n)的时间，所以总的时间复杂度是O(n)。重要的是要注意，这种复杂性不是使用随机方法的平均情况(例如必须考虑命中概率的哈希表)。这种复杂性在最坏情况下是相同的。