從三個矩陣算法中找出給定總數「總數」

我在跟隨this問題，我覺得這可以在O（NLogN）中解決。以下是我的算法：從三個矩陣算法中找出給定總數「總數」

1. Sort list1 , list2, list3 i.e. O(NLogN) 
2. while indexA < size and indexB < size and indexC < size //here size is the array size 
    int sum = a1[indexA] + a2[indexB] + a3[indexC] 
    if sum < total then choose the minimum value from a1, a2, a3 and increment that index 
    if sum > total print total can not be found and return 
    if sum == total then print the indexes 
    //this is O(N)

因此，所有總計O（NLogN）。請告訴我關於上述算法的正確性。

編輯

由於Muckle_ewe解釋說，這種算法中會在一些地方因此在進一步討論的算法中，而請評論的問題是否能爲O解決的是沒有意義的失敗（NLogN）如果是的話，算法，謝謝？

來源

2013-07-21 Trying

你能提出這個問題添加一些更詳細的嗎？謝謝！ – lsk

@ user1930928我有問題的鏈接int。請參閱。 – Trying

「打印總數無法找到並返回」是什麼意思？ –

沒有將失敗的

if sum < total then choose the minimum value from a1, a2, a3 and increment that index

線。考慮下面的反例（僞碼）

list1 = [1, 10] 
list2 = [2, 3] 
list3 = [3, 4]

讓總是7，對於該解決方案將是1 + 2 + 4（或1 + 3 + 3）。讓索引A = indexB = indexC = 0的初始總和然後

list1[0] + list2[0] + list3[0] 
1 + 2 + 3 = 6

由於這是小於7，我們增加這給了最小的列表值，這是作爲索引A list1的[索引A] = 1薩姆索引然後

list1[1] + list2[0] + list3[0] 
10 + 2 + 3 = 15

由於這是大於7的算法告訴我們有沒有辦法解決

來源

2013-07-21 00:19:28

很好的捕獲。涼。 +1 – Trying

從三個矩陣算法中找出給定總數「總數」

回答

相關問題