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
    }
}

LeetCode Solution, Easy, 136. Single Number

Comments

LeetCode Solution

More from this blog

如何開始入門軟體工程領域 - 名詞解釋（長期更新）

我的 MacBook Pro (Apple Silicon) 設定

ChatGPT 下的發展預想

一些覺得有用的工具蒐藏

LeetCode Solution, Medium, 607. Sales Person

136. Single Number

題目敘述

題目翻譯

解法解析

程式範例

Go

JavaScript

Kotlin

PHP

Python

Rust

Swift

Command Palette

Comments

LeetCode Solution

More from this blog

136. Single Number

題目敘述

題目翻譯

解法解析

程式範例

Go

JavaScript

Kotlin

PHP

Python

Rust

Swift