如何降低 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

将每个数组转换为映射，将出现的每个数字映射到该数字的出现次数 (&nbsp;map.compute( (key,prev) -> (prev==null ? 1 : prev+1) ))。这需要 O(N)计算所有映射中每个键的最小计数。也为 O(N)将所有最小计数相加即可得出答案。也是 O(N)。

Answer 2

我想复杂性甚至更糟，因为 contains() 还执行 for 循环。您可以创建3个包含A、B和C内容的集合，我将它们称为X_remaining。对于A_remaining中的每个元素，检查它是否包含在B_remaining和C_remaining中。如果是，则增加 c 并删除所有集合中找到的元素。尝试重复使用搜索结果，以免删除时再次搜索。要比线性更快地查找元素，可以使用 TreeSet。也许 HashSet 也是您的一个选择。

Answer 3

这是一种实现O(n^2)此任务复杂性的方法：private static int common(int[] A, int[] B, int[] C) {&nbsp;&nbsp; List<Integer> listA = Arrays.stream(A).boxed().collect(Collectors.toList());&nbsp; List<Integer> listB = Arrays.stream(B).boxed().collect(Collectors.toList());&nbsp; List<Integer> listC = Arrays.stream(C).boxed().collect(Collectors.toList());&nbsp; listA.retainAll(listB);&nbsp; listA.retainAll(listC);&nbsp; listB.retainAll(listA);&nbsp; listB.retainAll(listC);&nbsp; listC.retainAll(listA);&nbsp; listC.retainAll(listB);&nbsp; return Math.min(listA.size(), Math.min(listB.size(), listC.size()));}另外，IMO 你可以获得O(n)解决方案，例如：private static long common(int[] A, int[] B, int[] C) {&nbsp; Map<Integer, Long> frequencyA = findFrequencies(A);&nbsp; Map<Integer, Long> frequencyB = findFrequencies(B);&nbsp; Map<Integer, Long> frequencyC = findFrequencies(C);&nbsp; Set<Integer> common = frequencyA.keySet();&nbsp; common.retainAll(frequencyB.keySet());&nbsp; common.retainAll(frequencyC.keySet());&nbsp; return frequencyA.entrySet().stream()&nbsp; &nbsp; .filter(e -> common.contains(e.getKey()))&nbsp; &nbsp; .mapToLong(e -> Math.min(e.getValue(), Math.min(frequencyB.get(e.getKey()), frequencyC.get(e.getKey()))))&nbsp; &nbsp; .sum();}private static Map<Integer, Long> findFrequencies(int[] A) {&nbsp; return Arrays.stream(A)&nbsp; &nbsp; .boxed()&nbsp; &nbsp; .collect(Collectors.groupingBy(Integer::intValue, Collectors.counting()));}

Answer 4

您可以在此处使用 a HashMap，对于每个子列表，计算它在子列表中出现的次数。一个简单的 Haskell 程序如下所示：import Data.Hashable(Hashable)import Data.HashMap.Strict(HashMap, alter, elems, empty, intersectionWith)import Data.Maybe(maybe)toCounter :: (Eq a, Hashable a, Integral i) => [a] -> HashMap a itoCounter = foldr (alter (Just . maybe 1 (1+))) emptymergeCount :: (Eq a, Hashable a, Integral i) => HashMap a i -> HashMap a i -> HashMap a imergeCount = intersectionWith min然后我们可以用以下方法计算结果：calculateMinOverlap :: (Eq a, Hashable a, Integral i, Functor f, Foldable f) => f [a] -> icalculateMinOverlap = sum . elems . foldr1 mergeCount . fmap toCounter然后我们可以计算最小重叠：Main> calculateMinOverlap [[1,3,3,3,6], [3,3,1,5], [3,3,1,5,2]]3它需要元素总数的线性时间，并且该函数可以处理任意数量的子列表（假设至少有一个子列表）。所需toCounter时间与子列表大小呈线性关系O(m)。当我们执行 an 时，我们将在O(n)fmap toCounter中处理所有列表，其中n是元素总数。接下来的mergeCount工作时间为O(m 1 +m 2 )，其中m 1和m 2HashMap分别是两个 s中的元素数量。它每次都会返回一个HashMap包含多个元素的元素，该元素最多是两个元素中最小的一个。这意味着我们的foldr1 mergeCount工作时间也是O(n)。最后，我们在O(m)中检索elems结果的 ，其中m是最终 中的元素数量，并且也需要O(m) 。HashMapsum请注意，严格来说，对于巨大的数字，两个任意大数字的最小值等需要O(log v)，其中v是该数字的值。对于递增等也是如此。因此，如果对象数量很大，严格来说，它可以以O(n log n)进行缩放。