LeetCode #136 Single Number 只出現一次的數字

Klook.com
文章觀看次數: 308

英文原文如下

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.

中文翻譯

給予一個非空的整數陣列 nums，除了一個元素之外其他的元素都會出現兩次，找到出現一次的那個元素。

你的解答必須是線性時間複雜度，以及僅使用常數級的額外空間

( 線性時間複雜度 = O(n) )

範例及題目限制

解題思路

這一題剛開始沒認真看題目限制，直接寫了個簡單的 sort，然後迴圈來尋找不一樣的那個數字

但時間複雜度直接超出了限制

C# 解決方案

❌第一次嘗試

public class Solution {
    public int SingleNumber(int[] nums) {
        
        if(nums.Length == 1)
        {
            return nums[0];
        }
        Array.Sort(nums);
        
        for(int i=0;i<nums.Length;i++)
        {
            if(i != nums.Length-1)
            {
                if(nums[i+1]!=nums[i])
                {
                    return nums[i];
                }
                i+=1;
            }
            else
            {
                return nums[i];
            }
        }
        
        return 0;
    }
}

時間複雜度 : O(n log n) ➡ 就是因為Array.Sort

方案1 – 改用HashSet

public class Solution {
    public int SingleNumber(int[] nums) {
        HashSet<int>set = new HashSet<int>();

        foreach(var num in nums)
        {
            if(set.Contains(num))
            {
                set.Remove(num);
            }
            else
            {
                set.Add(num);
            }

        }

        return set.First();
    }
}

時間複雜度 : O(n)

改用HashSet後就符合答案了，因為HashSet的動作都接近 O(1)

Java解決方案

方案1

class Solution {
    public int singleNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<>();

        for (int num : nums) 
        {
            if (set.contains(num)) 
            {
                set.remove(num);
            } 
            else 
            {
                set.add(num);
            }
        }

        return set.iterator().next();
    }
}

Python3 解決方案

方案1

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        numSet = set()

        for num in nums:
            if num in numSet:
                numSet.remove(num)
            else:
                numSet.add(num)

        return numSet.pop()

JavaScript 解決方案

方案1

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    var numSet = new Set();

    for (let num of nums) 
    {
        if (numSet.has(num)) 
        {
            numSet.delete(num);
        } 
        else 
        {
            numSet.add(num);
        }
    }

    return numSet.values().next().value;
};

結論

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡收藏文章或幫我點個廣告，那都是對我的支持

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Single Number – LeetCode

一些隨機文章

相關文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *