小编use*_*810的帖子

在亚马逊采访中我问过这个问题 -

给定一个正整数数组,您必须找到无法从数组中的数字之和形成的最小正整数.

例:

Array:[4 13 2 3 1]
result= 11 { Since 11 was smallest positive number which can not be formed from the given array elements }

我做的是:

1. 排序数组
2. 计算前缀总和
3. 对求和数组进行求解并检查下一个元素是否小于1,即A [j] <=(sum + 1).如果不是这样,那么答案将是总和+ 1

但这是nlog(n)解决方案.

采访者对此并不满意,并在不到O(n log n)时间内提出解决方案.