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

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并尽早返回。

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

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

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

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

fun hasDuplicates(input: List<List<String>>): Boolean {
    input.asSequence().flatten()
        // .onEach {
        //     println("getting $it")
        // }
        .groupingBy { it }
        .aggregate { _, _: Int?, _, first ->
            if (first) {
                1
            } else {
                return true
            }
        }
    return false
}

累加器的类型(上面的 Int?)无关紧要，因为它未被使用。

但是，以下解决方案对我来说甚至更好，因为它允许我在所有都是唯一的情况下返回该集合，以后我需要:

fun uniqueOrNull(input: List<List<String>>): Set<String>? {
    return input.asSequence().flatten()
        .fold(mutableSetOf()) { seen, element ->
            if (!seen.add(element)) {
                return null
            }
            seen
        }
}

使用 aggregate也可以，但是效果却可以忽略不计，并且对读者来说更复杂:

fun uniqueOrNull(input: List<List<String>>): Set<String>? {
    return input.asSequence().flatten()
        .groupingBy { it }
        .aggregate { _, _: Int?, _, first ->
            if (first) {
                1
            } else {
                return null
            }
        }.keys
}