136.single-number.md

136. Single Number

Brute Force

fun singleNumber(nums: IntArray): Int {
    // skip    
}

• Time Complexity: O(n^2).
• Space Complexity: O(1).

Sorting

fun singleNumber(nums: IntArray): Int {
    nums.sort()
    for (i in 1 until nums.size step 2) {
        if (nums[i] != nums[i - 1]) return nums[i - 1]
    }
    return nums[nums.size - 1]
}

• Time Complexity: O(n lg n).
• Space Complexity: O(1).

Hash Table

fun singleNumber(nums: IntArray): Int {
    if (nums.size == 1) return nums[0]
    val countList = mutableListOf<Int>()
    for (i in 0 until nums.size) {
        if (countList.contains(nums[i])) {
            countList.remove(nums[i])
        } else {
            countList.add(nums[i])
        }
    }
    return countList.first()
}

• Time Complexity: O(n).
• Space Complexity: O(n).

Bit Manipulation

• A xor A = 0 (xor even times will be 0)
• A xor 0 = A (xor odd times will be itself)
• A xor B xor A is equals to A xor A xor B = B

fun singleNumber(nums: IntArray): Int {
    var result = nums[0]
    for (i in 1 until nums.size) {
        result = result xor nums[i]
    }
    return result
}

• Time Complexity: O(n).
• Space Complexity: O(1).