LeetCode #268 Missing Number 缺少的數字

Klook.com
文章觀看次數: 304

LeetCode題目翻譯

英文原文如下

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

中文翻譯

給予一個陣列 nums ，包含了 n 個唯一的數字，範圍為 0 到 n。回傳裡面缺少的數字

➡ 0 到 n 應有 n+1個數字，但缺少了一個

範例及題目限制

進階 : 你可以找出一個只有使用 O(1) 額外空間複雜度 跟 O(n) 時間複雜度的解決方法嗎?

解題思路

想當然，看到這題最簡單的解決方法就會是先對陣列進行排序，再一路檢查有沒有缺少的數字

而對陣列元素排序，大部分語言都有內建的語法可以使用

C# 解決方案

方案1

public class Solution {
    public int MissingNumber(int[] nums) {
        int n = nums.Length;
        Array.Sort(nums);

        if(nums[0]>0)
        {
            return 0;
        }

        for(int i =1; i<n;i++)
        {
            if(nums[i]-nums[i-1]>1)
            {
                return nums[i]-1;
            }
        }

        return n;
    }
}

時間複雜度 : O(n log n) + O(n) ≈ O(n log n)

額外空間複雜度 : O(1) ➡ 使用了一個變數 n

⭐方案2

public class Solution {
    public int MissingNumber(int[] nums) {
        return (1+nums.Length) * nums.Length /2 - nums.Sum();
    }
}

第二個解決方法比起第一個更簡單了

相信大家都知道 1加到 n的數學公式吧 !

沒錯~ 就是 (1+n)*n/2

雖然這個題目是從0開始，但不會影響到結果 (加上0會是一樣的結果)

時間複雜度 : O(n)

額外空間複雜度 : O(1)

Java解決方案

方案1

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);

        if (nums[0] > 0) {
            return 0;
        }

        for (int i = 1; i < n; i++) {
            if (nums[i] - nums[i - 1] > 1) {
                return nums[i] - 1;
            }
        }

        return n;
    }
}

⭐方案2

class Solution {
    public int missingNumber(int[] nums) {
        return (nums.length * (nums.length + 1) / 2) - Arrays.stream(nums).sum();
    }
}

Python3 解決方案

方案1

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        
        if nums[0] > 0:
            return 0
        
        for i in range(1, n):
            if nums[i] - nums[i-1] > 1:
                return nums[i] - 1
        
        return n

方案2

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        return (1 + len(nums)) * len(nums) // 2 - sum(nums)

JavaScript 解決方案

方案1

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    nums.sort((a, b) => a - b);
    let n = nums.length;
    
    if (nums[0] > 0) {
        return 0;
    }
    
    for (let i = 1; i < n; i++) {
        if (nums[i] - nums[i-1] > 1) {
            return nums[i] - 1;
        }
    }
    
    return n;
};

⭐需要注意的是JavaScript內建的 Array.sort() 會將元素以字串的方式進行排序

所以要進行改寫，不然本來的排序會變成 0 ➡ 1 ➡ 10 ➡2 … 類似這樣的

方案2

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    return (1 + nums.length) * nums.length / 2 - nums.reduce((sum, num) => sum + num, 0);
};

結論

這題算是沒甚麼難度，將答案縮減為一行就能解決看起來是不是很專業啊哈哈

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

🧡收藏文章或幫我分享，我都會很感謝的

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

題目連結 : Missing Number – LeetCode

一些隨機文章

相關文章

發佈留言

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