LeetCode之Single Number III（Kotlin）

2020-03-10 377 阅读1分钟

问题：

方法：解法不太好想，我也是看了题解才想明白，异或排重是知道的，但没想到这种用法，基本上这种找重复的题都是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