[LeetCode] 268. Missing Number 解題思路 (Easy)

這題要判斷陣列缺少的數字，陣列裡面元素會照著大小，但會有缺數字，如果沒缺則會是返回陣列的大小。

LeetCode 題目連結

 

https://leetcode.com/problems/missing-number/

 

題目

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Accept 作法

這題空間複雜度O(1)，但時間複雜度有排序所以是O(nlogn)。


Runtime: 5 ms
Memory: 40.5 MB

Java 程式碼

class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        for(int i = 0;i<nums.length;i++){
            if(i != nums[i]){
                return i;
            }
        }
        return nums[nums.length - 1]+1;
    }
}

 

更多 LeetCode 相關資源

• Udemy 暢銷 - Master the Coding Interview: Data Structures + Algorithms

 

複習程式面試書籍

除了 LeetCode 練習外，我也入手了這本，題庫來自真正的面試，並非摘自教科書。它們反映出頂尖公司真正會出的題目，你可以藉此做好充分準備。
需要的話可以看看，寫得很仔細。

書名：提升程式設計師的面試力：189道面試題目與解答

• 金石堂實體書資訊
• Hyread 電子書資訊

相關 LeetCode文章一律會放在 程式解題 標籤分類，歡迎持續追蹤。

⇒ 點我看更多程式解題