c# - 如何实现该函数的最坏情况时间复杂度为 O(n)？

Question

我在执行某项任务时遇到问题。这不是作业或其他什么，现在更像是个人问题。我想知道是否有解决方案......

重点是实现函数的预期 O(n) 最坏情况时间复杂度，该函数采用 2 个字符串数组作为输入(我们将第一个数组称为 A ，将第二个数组称为 B )，并且应该返回一个整数数组，其中每个元素代表数组 A 中相应元素的索引。

所以，函数应该是这样的:

private static int[] GetExistingStrings(string[] A, string[] B) { ... }

• 数组 A 包含所有可能的名称
• 数组 B 包含应排除的名称(即，如果存储在 B 数组中的某些名称也在 A 数组中，则它们的索引不应包含在输出 int[] 数组中；该数组也可能可以包含一些随机字符串，这些字符串不一定出现在 A 数组中，甚至可能为空。

例如，如果我们有这些数组:

string[] A = { "one", "two", "three", "four" }; // 0, 1, 2, 3
string[] B = { "two", "three" }; // Indices of "two" and "three" not taken into account

该函数应返回:

int[] result = { 0, 3 }; // Indices of "one" and "four"

首先，我尝试采用明显且简单的方法(使用嵌套 for 循环):

private static int[] GetExistingStrings(string[] A, string[] B)
{
    LinkedList<int> aIndices = new LinkedList<int>();

    for (int n = 0; n < A.Length; n++)
    {
        bool isExcluded = false;
        for (int m = 0; m < B.Length; m++)
        {
            if (A[n].Equals(B[m]))
            {
                isExcluded = true;
                break;
            }
        }

        if (!isExcluded)
        {
            aIndices.AddLast(i);
        }
    }

    int[] resultArray = new int[aIndices.Count];
    aIndices.CopyTo(resultArray, 0);
    return resultArray;
}

我使用 LinkedList 是因为我们不可能知道输出的数组大小应该是多少，而且还因为向此列表添加新节点是一个常数 O(1) 操作。当然，这里的问题是这个函数(正如我假设的那样)的时间复杂度是O(n*M)。所以，我们需要寻找另一种方法......

我的第二种方法是:

private static int[] GetExistingStrings(string[] A, string[] B)
{
    int n = A.Length;
    int m = B.Length;

    if (m == 0)
    {
        return GetDefaultOutputArray(n);
    }

    HashSet<string> bSet = new HashSet<string>(B);
    LinkedList<int> aIndices = new LinkedList<int>();

    for (int i = 0; i < n; i++)
    {
        if (!bSet.Contains(A[i]))
        {
            aIndices.AddLast(i);
        }
    }

    if (aIndices.Count > 0)
    {
        int[] result = new int[aIndices.Count];
        aIndices.CopyTo(result, 0);
        return result;
    }

    return GetDefaultOutputArray(n);
}

// Just an utility function that returns a default array
// with length "arrayLength", where first element is 0, next one is 1 and so on...
private static int[] GetDefaultOutputArray(int arrayLength)
{
    int[] array = new int[arrayLength];
    for (int i = 0; i < arrayLength; i++)
    {
        array[i] = i;
    }
    return array;
}

这里的想法是将 B 数组的所有元素添加到 HashSet 中，然后使用它的方法 Contains() 在 for 循环中检查是否相等。但我无法完全计算这个函数的时间复杂度...我确信 for 循环中的代码将执行 n 次。但最让我烦恼的是 HashSet 初始化——这里应该考虑它吗？它如何影响时间复杂度？这个函数是O(n)吗？或者由于 HashSet 初始化而导致 O(n+m)？

有没有办法解决这个任务并实现O(n)？

Answer 1

如果A中有n个元素，B中有m个元素，并且字符串的长度k， HashMap 方法的预期时间是O(k*(m + n))。不幸的是，如果哈希算法不起作用，最坏的时间是O(km(m + n))。 (几率非常低。)我以前也犯过这个错误，感谢@PaulHankin 的纠正。

为了获得O(k*(m + n))最差时间，我们必须采取一种非常不同的方法。你要做的就是构建一个 trie现在，您将遍历 A 的每个元素并在 trie 中查找它。与哈希不同，特里树保证了最坏情况下的性能(更好的是，即使我们不使用前缀查找，也可以进行前缀查找)。这种方法不仅为我们提供了预期的平均时间O(k*(m + n))，而且还为我们提供了同样的最差时间。

您无法做得比这更好，因为仅处理列表就需要处理 O(k*(m + n)) 数据。