我正在閱讀演算法簡介，在那里我遇到了 ex 2.3-7。
經過深思熟慮，我意識到蠻力演算法需要 O(nlogn)：
bool exactSum(int arr[], const int &length, const int &value) {
bool isExact = false;
for(unsigned i = 0; i < length - 1; i) {
for(unsigned j = i 1; j < length; j) {
if(arr[i] arr[j] == value) {
isExact = true;
break;
}
}
}
return isExact;
}
你看，只有 nlogn 檢查。我錯了嗎？
uj5u.com熱心網友回復：
您描述的演算法需要 O(n^2) 時間復雜度，因為在最壞的情況下，有 n*(n-1)/2 比較。
@Shridhar R Kulkarni 的所有功勞，他指出即使沒有排序也可以解決這個問題。
在這種情況下，您將需要使用哈希映射。將陣列的元素及其各自的計數存盤在哈希圖中。現在，迭代陣列元素。假設你在 index i。只需檢查(value - are[i])哈希圖中是否存在。
時間復雜度 = O(n)。
特殊情況
當arr[i]等于 時value - arr[i]，檢查元素的計數arr[i]是否大于 1 是否存在一對。
特殊情況的學分 - @Dillon Davis。
uj5u.com熱心網友回復：
@Deepak 發布的答案對于這篇文章來說已經足夠了。但是，您可以進一步簡化。對于 a b = value 和 a = b 的情況，字典方法需要兩次迭代和額外的條件處理。相反，您可以通過使用無序集在一次迭代中完成，實際上空間更小。
偽代碼：
for element in array:
if value - element in unordered_set:
return true
unordered_set.add(element)
return false
Time complexity: O(n)
Space complexity: O(n)
使用與上述相同的邏輯，您可以使字典/哈希圖與單次迭代一起作業，以避免額外的迭代來獲取計數。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/406487.html
標籤：