阅读 52

LeetCode之Single Number III(Kotlin)

问题:


方法: 解法不太好想,我也是看了题解才想明白,异或排重是知道的,但没想到这种用法,基本上这种找重复的题都是HashMap或者位图法,本方法应该是位图法的延伸,不是通过位去记录数字而是存储差异,最后通过差异过滤出目标结果。

class SingleNumberIII {
    fun singleNumber(nums: IntArray): IntArray {
        var bitMask = 0
        nums.forEach { bitMask = bitMask.xor(it) }
        val bitPos = bitMask.and(-bitMask)
        var x = 0
        nums.filter { it.and(bitPos) != 0}.forEach {
            x = x.xor(it)
        }
        return intArrayOf(x, bitMask.xor(x))
    }
}

fun main(args: Array<String>) {
    val input = intArrayOf(2, 1, 2, 3, 4, 1)
    val singleNumberIII = SingleNumberIII()
    CommonUtils.printArray(singleNumberIII.singleNumber(input).toTypedArray())
}
复制代码

有问题随时沟通

具体代码实现可以参考Github