首先,让我们勾勒出解决方案的想法。
随着foldRight
,你只能从右到左逐个处理项目,维护一个累加器。
的问题是,对于一个项目在i
位置时,dropWhile
逻辑作出决定是否包括项到结果或不基于是否存在在j <= i
不满足谓词位置的项(包括如果是)。这意味着你不能简单地维护结果项目:对于你已经处理的一些项目,你不知道它们是否应该被包含在内。
例子:
(我们正在处理从右到左的项目,所以前缀是未知的我们)
... (some unknown items) ... ... ... ... a b c d <--- (right-to-left)
predicate satisfied: T T F T
我们发现在左边的详细项目,有有两种可能性:
我们发现该序列的开始,并且没有物品谓词给F
:
(the sequence start) y z a b c d <--- (right-to-left)
predicate satisfied: T T T T F T
-------
drop
在这种情况下,应删除前缀y z a b
。
我们发现,不满足谓词的项目:
... (some unknown items) ... w z a b c d <--- (right-to-left)
predicate satisfied: F T T T F T
-------
include
只有在这一点上,我们确实知道,我们需要包括项目w z a b
,我们无法做到这一点早,因为可能有序列的开始而不是项目w
,然后我们应该丢掉z a b
。
但需要注意的是,在这两种情况下,我们确信c d
是项目纳入结果:这是因为他们有c
与F
谓语在他们面前。
鉴于此,可以清楚地看到,在处理项目时从右到左,可以维护一个不能确定被纳入结果项的单独列表,它们可以是被丢弃或当遇到一个false
谓词结果时,以及给出这样的false
结果的项目。
我的实现:
我用一对两个列表的用于蓄能器,其中所述第一列表是针对一定要包括的项目,而第二个用于那些不是。
fun <T> List<T>.myDropWhile(predicate: (T) -> Boolean) =
foldRight(Pair(emptyList<T>(), emptyList<T>())) { item, (certain, uncertain) ->
if (predicate(item))
Pair(certain, uncertain + item) else
Pair(certain + uncertain + item, emptyList())
}.first.reversed()
实施例:
val ints = listOf(0, 0, 0, 1, 0, 2, 3, 0, 0, 4)
println(ints.myDropWhile { it == 0 }) // [1, 0, 2, 3, 0, 0, 4]
参见:runnable demo of this code with more tests。
注:在每次迭代做uncertain + item
或certain + uncertain + item
复制只读列表给出O(n^2)
最坏情况下的时间复杂度,这是不切实际的。使用可变数据结构给出O(n)
时间。