java - 如何降低 O(n^3) 的复杂性？ (提供代码)

Question

我正在编写此方法来查找 3 个数组中常见数字的数量(允许重复，例如 if A=[1,3,3,3,6], B=[3,3, 1,5], C=[3,3,1,5,2] 然后方法应该返回 3；两个 3 + 一个 1)。我使用了 3 个 for 循环，但我觉得应该有更好的方法。

这是我的代码:

private static int common(int[] A, int[] B, int[] C)
{
    int c=0;
    List<Integer> visitedBs=new ArrayList<Integer>(), visitedCs=new ArrayList<Integer>();

    for (int i = 0; i < A.length; i++)
        outerloop:
        for (int j = 0; j <B.length ; j++)
            if (A[i]==B[j] && !visitedBs.contains(j))
                for (int k = 0; k < C.length; k++)
                    if (B[j] == C[k] && !visitedCs.contains(k)) {
                        c++;
                        visitedBs.add(j);
                        visitedCs.add(k);
                        break outerloop;
                    }

    return c;
}

有人知道我应该如何降低时间复杂度吗？有没有办法改用 2 个 for 循环？

Answer 1

我猜复杂度甚至更糟，因为 contains() 也执行 for 循环。

您可以创建 3 个包含 A、B 和 C 内容的集合，我将它们称为 X_remaining。对于 A_remaining 中的每个元素，检查它是否包含在 B_remaining 和 C_remaining 中。如果是这样，递增 c 并删除所有集合中找到的元素。尝试重新使用搜索结果，以便在删除时不再搜索。

要比线性查找元素更快，您可以使用 TreeSet。也许 HashSet 也是您的一个选择。