136. Single Number

題目敘述

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

Constraints:

• 1 <= nums.length <= 3 * 10**4
• -3 * 10**4 <= nums[i] <= 3 * 10**4
• Each element in the array appears twice except for one element which appears only once.

題目翻譯

給定一個整數的陣列 nums，其中的元素都是兩兩成對的加上一個單一的數值。從陣列 nums 中找出是哪一個數值是只有單獨的一個。(情人節剛結束出這題是想嘲諷單身狗？！

解法解析

這題讓我想到前幾天的 LeetCode Solution, Easy, 389. Find the Difference 的解題邏輯一樣，找出不同的數值。所以使用 Bit operator 是最快速的方式，讓 Time complexity 可以為 O(n)，且 Space complexity O(1)。這邊唯一不同的是 PHP，因為有內建的計算函數，所以直接使用。

程式範例

Go

func singleNumber(nums []int) int {
    res := 0
    for _, n := range nums {
        res = res ^ n
    }
    return res
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
    let result = 0;
    for (let i of nums) {
        result ^= i;
    }
    return result;
};

Kotlin

class Solution {
    fun singleNumber(nums: IntArray): Int {
        var result: Int = 0
        for (i in nums) {
            result = result xor i
        }
        return result
    }
}

PHP

class Solution
{

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function singleNumber($nums)
    {
        $count_nums = array_count_values($nums);
        foreach ($count_nums as $key => $value) {
            if ($value == 1) {
                return $key;
            }
        }
    }
}

Python

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        """
        :type nums: List[int]
        :rtype: int
        """
        a = 0
        for i in nums:
            a ^= i
        return a

Rust

impl Solution {
    pub fn single_number(nums: Vec<i32>) -> i32 {
        let mut res = 0;
        for num in nums {
            res ^= num;
        }
        res
    }
}

Swift

class Solution {
    func singleNumber(_ nums: [Int]) -> Int {
        var sum = 0
        for num in nums {
            sum ^= num
        }
        return sum
    }
}