我得到了一个整数数组A。现在我必须找出一个子数组(原始数组的子序列),其中每对数字的总和大于或等于预定义的K。
我的想法是:
- 将数组按照值的范围排序为O(nlgn)或O(n)。 - 找到排序后的数组中的i,使得
运行时间:O(nlgn)
这个解决方案是否最优?我们能否进一步改进它?
例子:
我的想法是:
- 将数组按照值的范围排序为O(nlgn)或O(n)。 - 找到排序后的数组中的i,使得
sorted[i] + sorted[i+1]>=k
。
- 将max设置为sorted[i]
。
- 遍历原始数组以删除所有小于max的值,这是所需的子序列。
- 对数组的所有元素重复上述操作。运行时间:O(nlgn)
这个解决方案是否最优?我们能否进一步改进它?
例子:
-10 -100 5 2 4 7 10 23 81 5 25
排序数组
-100 -10 2 4 5 5 7 10 23 25 81
让 K = 20
子数组:-
10 23 25 81
如果问题是找到最长的子数组,alestanis在答案中提出的算法将很好地工作 :)
i
,使得array[i] + array[i+1] >= K
。 - Eduardo5+10
打破了这个规则... - raina77ow