LeetCode — Missing Number
Jan 25, 2022
題目連結:268. Missing Number
難度:easy
題目大意:
檢查測資 vector 中遺失的數字為何。
解題過程:
【version 1 — binary search】
1. 排序 nums
2. 用 binary search 搜尋哪邊有 missing number
【version 2】
1. 將 0~nums.size()+1 大小的所有值加總為 sum
2. 透過迴圈將 vector 中所有值從 sum 扣除掉
3. 回傳 sum 剩餘的值
使用語言:C++
實作程式如下:
時間複雜度:O(N*logN+logN),排序及 binary search
空間複雜度:O(1)
Runtime: 37 ms, faster than 21.33% of C++ online submissions for Missing Number.
Memory Usage: 18 MB, less than 18.54% of C++ online submissions for Missing Number.
時間複雜度:O(N)
空間複雜度:O(1)
Runtime: 36 ms, faster than 23.16% of C++ online submissions for Missing Number.
Memory Usage: 18.1 MB, less than 18.54% of C++ online submissions for Missing Number.