我應該以盡可能低的時間復雜度來解決這個問題，但讓我更具體一些。
你得到一個包含重復的整數的排序陣列。
唯一四元組是一組四個索引。這些索引下的陣列元素的總和必須為給定值 X。例如：
給定一個陣列 [10, 20, 30, 40] 和 X = 100，只有一個四元組：(0, 1, 2, 3)。
給定一個陣列 [0, 0, 0, 0, 0] 和 X = 0，有 5 個四元組：(0, 1, 2, 3), (0, 1, 2, 4), (0, 1, 3 , 4), (0, 2, 3, 4), (1, 2, 3, 4)。
在互聯網上有很多 N^3 解決方案，但這些解決方案是針對價值而非索引的獨特四倍。在這些解決方案中，例如沒有。1 仍然只給出一個四倍數：(10, 20, 30, 40)，但是沒有例子。2 只給出一個四元組 (0, 0, 0, 0)，而不是五個。
我找不到可以解決我的問題而不是另一個問題的 O(N^3) 解決方案。我可以很容易地撰寫一個在 O(N^3logN) 時間內解決它的程式。我還聽說這個問題的較低復雜性界限據稱是未知的。是否有已知的 O(N^3) 解決方案？
我知道的解決方案：
- 明顯的幼稚方法 O(N^4)：
int solution(int arr[], int arrSize, int X){
int counter = 0;
for(int i=0; i<arrSize-3; i)
for(int j=i 1; j<arrSize-2; j)
for(int k=j 1; k<arrSize-1; k)
for(int l=k 1; l<arrSize; l)
if(arr[i] arr[j] arr[k] arr[l] == X) counter;
return counter;
}
- 使用三元組和二進制搜索 O(N^3logN) 的方法：
int solution(int arr[], int arrSize, int X){
int counter = 0;
for(int i=0; i<arrSize-3; i)
for(int j=i 1; j<arrSize-2; j)
for(int k=j 1; k<arrSize-1; k){
int subX = X - arr[i] - arr[j] - arr[k];
int first = binFirst(subX, arr, k 1, arrSize);
//binary search that returns position of first
//occurence of subX in arr in range [k 1, arrSize)
//or -1 if not found
int last = binLast(subX, arr, k 1, arrSize);
//binary search that returns position of last
//occurence of subX in arr in range [k 1, arrSize)
//or -1 if not found
if(first != -1) counter = last - first 1;
return counter;
當然，可以通過計算 arr[i]、arr[j]、arr[k] 的所有重復項來改進上述演算法，但據我所知，它并沒有降低實際的 O(N^3logN) 復雜度。
uj5u.com熱心網友回復：
我們可以O(n^2)通過動態更新在時間和空間上做到這一點。
首先創建 sum 的哈希映射到組成它的元組集合，從左側遍歷，并為每個索引存盤它所屬的元組（其中的 O(n) 個），直到剩下右側的兩個元素和沒有散??列。
現在向左遍歷：從最右邊的第三個元素開始，洗掉當前元素所屬的所有元組（O(n) 個）。然后，對于元素可以通過與其右側的元素配對創建的每個總和，將元組的計數添加到相應的散列總和中，以完成總和。因為我們洗掉了左側使用當前元素的所有實體，所以我們保證有磁區的四元組，其中右側的任何實體都沒有在左側的散列計數中表示。
uj5u.com熱心網友回復：
Python 中的 O(n2)，靈感來自 ???? ???? 的回答：
from itertools import combinations
from collections import Counter
def solution(arr, X):
cd = Counter(map(sum, combinations(arr, 2)))
count = 0
for i, b in enumerate(arr):
for d in arr[i 1:]:
cd[b d] -= 1
for a in arr[:i]:
count = cd[X - (a b)]
return count
打電話給四人組(a,b,c,d)。我們專注于第二個元素，b。對于每個可能的b，我們添加每個可能的a（ 左邊的元素b），并查找有多少對(c,d)（ 右邊的元素b）完成了 sum a b c d = X，即 sum to X - (a b)。對于該查找，我們有一個哈希映射cd，它將對的總和映射到對的計數。最初，這是所有對的整體arr，但對于b我們考慮的每一個，洗掉它對地圖的貢獻。
C 版本，其中 a/b/c/d 是索引而不是元素：
int solution(int arr[], int n, int X){
std::unordered_map<int, int> cd;
for (int c=0; c<n; c )
for (int d=c 1; d<n; d )
cd[arr[c] arr[d]] ;
int count = 0;
for (int b=0; b<n; b ) {
for (int d=b 1; d<n; d )
cd[arr[b] arr[d]]--;
for (int a=0; a<b; a )
count = cd[X - (arr[a] arr[b])];
}
return count;
}
帶測驗的 Python 代碼（在線試用！）：
from itertools import combinations
from collections import Counter
def solution(arr, X):
cd = Counter(map(sum, combinations(arr, 2)))
count = 0
for i, b in enumerate(arr):
for d in arr[i 1:]:
cd[b d] -= 1
for a in arr[:i]:
count = cd[X - (a b)]
return count
import random
from operator import countOf
def naive(arr, X):
sums = map(sum, combinations(arr, 4))
return countOf(sums, X)
arr = random.choices(range(100), k=100)
print(naive(arr, 200))
print(solution(arr, 200))
帶有測驗的 C 代碼。
uj5u.com熱心網友回復：
陣列已排序，這意味著我們可以使用二進制搜索。
現在，如果我們創建pairs包含對的總和，例如
arr = [10, 20, 30, 40]
pairs = [10 20, 10 30, 10 40, 20 30, 20 40, 30 40]
有一個模式，10 x 有 3 對，20 x 有 2 對，30 x 有 1 對，40 x 有 0 對。
[10 20, 10 30, 10 40, 20 30, 20 40, 30 40]
# ------------------- ------------ -----
[30, 40, 50, 50, 60, 70]
# ---------- ------ --
所以，總對是
3 2 1
= sum of first (n-1) natural numbers
= (n - 1) * (n - 1 1) / 2
= (n - 1) * n / 2
= (n^2 - n) / 2
看起來整個pairs陣列都會被排序，但事實并非如此，pairs應該對其中的那些子陣列進行排序，因為初始arr是排序的。例如
arr = [10, 20, 30, 90]
pairs = [10 20, 10 30, 10 90, 20 30, 20 90, 30 90]
# Those sub-arrays are sorted
[30, 40, 100, 50, 110, 120]
# ----------- ------- ---
現在，讓我們撰寫pairs原點arr索引
pairs = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
(0, 1)并且(0, 2)不是有效的四元組，因為我們0在兩對中都有那么，我們如何在邏輯上找到有效的對呢？
我們只有一對有效的配對，(0, 1)其中(2, 3)沒有0或1
[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
# x x x x x x ----
一個事實是，我們總是可以用這樣的方式寫四倍，一對緊挨著另一對，例如
x = 100
arr = [10, 20, 30, 40]
pairs = [30, 40, 50, 50, 60, 70]
[10, 20, 30, 40]
# -- ------ --
quadruple = (10 40) (20 30)
# which can we re-written as
[10, 20, 30, 40]
# ------ ------
quadruple = (10 20) (30 40) = 30 70
# Which is as follows
pairs = [30, 40, 50, 50, 60, 70]
# -- --
因此，我們可以按照以下方式解決問題
for pair0 in pairs:
valid_pairs_for_pair0 = # Somehow get the valid pairs
for pair1 in valid_pairs_for_pair0:
if pair0 pair1 == x:
ans = 1
但上面的解決方案是O(n^4)因為pairs是長度(n^2 - n) / 2
我們可以做得更好，因為我們知道對中的那些子陣列是排序的
arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] # n = 10
pairs = [
(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(0,9),# (0,x) -> 9 pairs -> 10 - 0 - 1
(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),# (1,x) -> 8 pairs -> 10 - 1 - 1
(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),# (2,x) -> 7 pairs -> 10 - 2 - 1
(3,4),(3,5),(3,6),(3,7),(3,8),(3,9),# (3,x) -> 6 pairs -> 10 - 3 - 1
(4,5),(4,6),(4,7),(4,8),(4,9),# (4,x) -> 5 pairs -> 10 - 4 - 1
(5,6),(5,7),(5,8),(5,9),# (5,x) -> 4 pairs -> 10 - 5 - 1
(6,7),(6,8),(6,9),# (6,x) -> 3 pairs -> 10 - 6 - 1
(7,8),(7,9),# (7,x) -> 2 pairs -> 10 - 7 - 1
(8,9),# (8,x) -> 1 pair -> 10 - 8 - 1
]
# we need to find the first valid pair and all of the pairs after that will be valid.
first valid pair index for (0, 1) => first (2,x) pair => (2,3) => pairs[9 8]
first valid pair index for (0, 2) => first (3,x) pair => (3,4) => pairs[9 8 7]
first valid pair index for (0, 3) => first (4,x) pair => (4,5) => pairs[9 8 7 6]
# There is a pattern
pairs[9 8] => pairs[sum(9 to 1) - sum(7 to 1)]
pairs[9 8 7] => pairs[sum(9 to 1) - sum(6 to 1)]
pairs[9 8 7 6] => pairs[sum(9 to 1) - sum(5 to 1)]
# Thats how we get started and for binary search
start = firstNSum(n - 1) - firstNSum(n - i1 - 2)
end = start n - (i1 1) - 1 # n - (i1 1) - 1 is the number of pairs for (i1,x) pairs
現在，我們可以解決以下問題
# for pair0 in pairs:
# binary search for all valid sub-arrays of pairs for pair0
時間復雜度：O(n^3.log(n)) log(n) log(n-1) ... log(1) = log(n!) = n.log(n)
空間復雜度：O(n^2)
def firstNSum(n):
return n * (n 1) // 2
def binary_search(pairs, x, start, end):
while start < end:
mid = (start end) // 2
if pairs[mid][1] < x:
start = mid 1
else:
end = mid
return start
def count_four_pairs_with_sum(arr, n, x):
ans = 0
pairs = []
for i0 in range(n - 1):
for i1 in range(i0 1, n):
curr_sum = arr[i0] arr[i1]
pairs.append([(i0, i1), curr_sum])
for [(i0, i1), curr_sum] in pairs:
start = firstNSum(n - 1) - firstNSum(n - i1 - 2)
end = start n - (i1 1) - 1
while start < len(pairs):
x_start = binary_search(pairs, x - curr_sum, start, end)
x_end = binary_search(pairs, x - curr_sum 1, start, end)
ans = x_end - x_start
i1 = 1
start = n - i1 - 1
end = start n - (i1 1) - 1
return ans
arr = [10, 20, 30, 40]
n = len(arr)
x = 100
print(count_four_pairs_with_sum(arr, n, x))
我們可以做得更好，如果我們用 sum 存盤對的數量，同時存盤來自每個 (i,x) 對組的對數pairs
# loop for i0
# loop for i1
# ans = valid pairs for i0 and i1, which is sum of i1 to n excluding i0 to i1
時間復雜度：O(n^3)
空間復雜度：O(n^3)
from collections import defaultdict
def count_four_pairs_with_sum(arr, n, x):
ans = 0
sum_freq = defaultdict(lambda: defaultdict(int))
for i0 in range(n - 1):
for i1 in range(i0 1, n):
curr_sum = arr[i0] arr[i1]
sum_freq[curr_sum][i0] = 1
for i0 in range(n - 1):
for i1 in range(i0 1, n):
curr_sum = arr[i0] arr[i1]
needed_sum = x - curr_sum
valid_needed_sum_count = sum([sum_freq[needed_sum][i] for i in range(i1 1, n)])
ans = valid_needed_sum_count
return ans
arr = [0, 0, 0, 0, 0]
n = len(arr)
x = 0
print(count_four_pairs_with_sum(arr, n, x))
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/523852.html
標籤：算法时间复杂度