我正在編寫這個方法來查找 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循環代替？
4 回答
慕的地6264312
TA貢獻1817條經驗 獲得超6個贊
將每個數組轉換為映射，將出現的每個數字映射到該數字的出現次數 ( map.compute( (key,prev) -> (prev==null ? 1 : prev+1) ))。這需要 O(N)
計算所有映射中每個鍵的最小計數。也為 O(N)
將所有最小計數相加即可得出答案。也是 O(N)。
小怪獸愛吃肉
TA貢獻1852條經驗 獲得超1個贊
我想復雜性甚至更糟，因為 contains() 還執行 for 循環。
您可以創建3個包含A、B和C內容的集合，我將它們稱為X_remaining。對于A_remaining中的每個元素，檢查它是否包含在B_remaining和C_remaining中。如果是，則增加 c 并刪除所有集合中找到的元素。嘗試重復使用搜索結果，以免刪除時再次搜索。
要比線性更快地查找元素，可以使用 TreeSet。也許 HashSet 也是您的一個選擇。
慕田峪4524236
TA貢獻1875條經驗 獲得超5個贊
這是一種實現O(n^2)此任務復雜性的方法：
private static int common(int[] A, int[] B, int[] C) {
List<Integer> listA = Arrays.stream(A).boxed().collect(Collectors.toList());
List<Integer> listB = Arrays.stream(B).boxed().collect(Collectors.toList());
List<Integer> listC = Arrays.stream(C).boxed().collect(Collectors.toList());
listA.retainAll(listB);
listA.retainAll(listC);
listB.retainAll(listA);
listB.retainAll(listC);
listC.retainAll(listA);
listC.retainAll(listB);
return Math.min(listA.size(), Math.min(listB.size(), listC.size()));
}
另外，IMO 你可以獲得O(n)解決方案，例如：
private static long common(int[] A, int[] B, int[] C) {
Map<Integer, Long> frequencyA = findFrequencies(A);
Map<Integer, Long> frequencyB = findFrequencies(B);
Map<Integer, Long> frequencyC = findFrequencies(C);
Set<Integer> common = frequencyA.keySet();
common.retainAll(frequencyB.keySet());
common.retainAll(frequencyC.keySet());
return frequencyA.entrySet().stream()
.filter(e -> common.contains(e.getKey()))
.mapToLong(e -> Math.min(e.getValue(), Math.min(frequencyB.get(e.getKey()), frequencyC.get(e.getKey()))))
.sum();
}
private static Map<Integer, Long> findFrequencies(int[] A) {
return Arrays.stream(A)
.boxed()
.collect(Collectors.groupingBy(Integer::intValue, Collectors.counting()));
}
GCT1015
TA貢獻1827條經驗 獲得超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 i
toCounter = foldr (alter (Just . maybe 1 (1+))) empty
mergeCount :: (Eq a, Hashable a, Integral i) => HashMap a i -> HashMap a i -> HashMap a i
mergeCount = intersectionWith min
然后我們可以用以下方法計算結果：
calculateMinOverlap :: (Eq a, Hashable a, Integral i, Functor f, Foldable f) => f [a] -> i
calculateMinOverlap = 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)進行縮放。
添加回答
舉報
0/150
提交
取消