1

i was following the this question and i felt that this can be solved in O(NLogN). Below is my algorithm:

 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)

Hence all total O(NLogN). Please tell me about the correctness of the above algo.

EDIT

As Muckle_ewe has explained that this algo will fail in some places so there is no point in further discussing on the algo rather please comment whether the question can be solvable in O(NLogN) if so then algo, thanks?

4

1 回答 1

3

不，那会失败

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）。令 indexA = indexB = indexC = 0。初始总和为

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

由于这小于 7，我们增加了给出最小列表值的索引，即 indexA 为 list1[indexA] = 1。然后总和

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

由于这大于 7，您的算法告诉我们没有解决方案

于 2013-07-21T00:19:28.690 回答