检查列表是否具有重复元素的功能方法

Question

我有一个元素列表，并想检查是否有重复项。我也想早点休息-我不在乎重复的是什么，也不管是否有很多，我只想知道是否至少有一个。

适合该法案的必要方法是：

fun main() {
    println(hasDuplicates(listOf(
        listOf("1", "2", "3"),
        listOf("4", "5"),
        listOf("1", "2")
    )))
}

fun hasDuplicates(input: List<List<String>>): Boolean {
    val seen = mutableSetOf<String>()
    input.forEach { inner ->
        inner.forEach { element ->
            if (!seen.add(element)) {
                return true
            }
        }
    }
    return false
}

没有显式迭代的另一种方法是：

fun hasDuplicates(input: List<List<String>>): Boolean {
    val flat = input.flatten()
    return flat.size != flat.toSet().size
}

但是这会迭代整个列表，甚至在第一步中创建一个扁平化的中介。

我有一个主意，但不知道如何实现：假设我可以将每个（扁平化的）列表元素映射到已经可见的次数。到目前为止，我有这个：

fun hasDuplicates(input: List<List<String>>): Boolean {
    return input.asSequence().flatten()
//        .onEach {
//            println("getting $it")
//        }
        .groupingBy { it }
        .eachCount()
        .any { (_, count) -> count > 1 }
}

它做了它应该做的，但首先迭代整个列表（取消对onEach中介的评论）以收集组。这个想法将逐步发出元素及其计数，例如（对于输入列表[“ 1”，“ 2”，“ 1”]：

// (element, seenCount)
("1", 0)
("2", 0)
("1", 1)

此时，我可以简单地检查seenCount > 0并提早返回。

有帮助吗？也欢迎任何其他想法。

UPDATE：得到了这个，虽然不是最初的想法，但似乎可行：

fun hasDuplicates(input: List<List<String>>): Boolean {
    input.asSequence().flatten()
        .onEach {
            println("getting $it")
        }
        .fold(mutableSetOf<String>()) { seen, element ->
            if (!seen.add(element)) {
                return true
            }
            seen
        }
    return false
}

上面的代码比最差版本的第一个版本稍差一些（没有重复项），在最佳情况下（第二个元素是重复项）和“中等”情况（中间的元素）几乎相同展平的列表是重复的）。

Answer 1

问题中描述的想法可以通过以下方式实现：