C++實現LeetCode(35.搜索插入位置)
[LeetCode] 35. Search Insert Position 搜索插入位置
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Example 1:
Input: [1,3,5,6], 5
Output: 2
Example 2:
Input: [1,3,5,6], 2
Output: 1
Example 3:
Input: [1,3,5,6], 7
Output: 4
Example 4:
Input: [1,3,5,6], 0
Output: 0
這道題基本沒有什麼難度,實在不理解為啥還是 Medium 難度的,完完全全的應該是 Easy 啊(貌似現在已經改為 Easy 類瞭),三行代碼搞定的題,隻需要遍歷一遍原數組,若當前數字大於或等於目標值,則返回當前坐標,如果遍歷結束瞭,說明目標值比數組中任何一個數都要大,則返回數組長度n即可,代碼如下:
解法一:
class Solution { public: int searchInsert(vector<int>& nums, int target) { for (int i = 0; i < nums.size(); ++i) { if (nums[i] >= target) return i; } return nums.size(); } };
解法二:
class Solution { public: int searchInsert(vector<int>& nums, int target) { if (nums.back() < target) return nums.size(); int left = 0, right = nums.size(); while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) left = mid + 1; else right = mid; } return right; } };
到此這篇關於C++實現LeetCode(35.搜索插入位置)的文章就介紹到這瞭,更多相關C++實現搜索插入位置內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- C++實現LeetCode(33.在旋轉有序數組中搜索)
- C++實現LeetCode(34.在有序數組中查找元素的第一個和最後一個位置)
- C++實現LeetCode(162.求數組的局部峰值)
- C++實現LeetCode(81.在旋轉有序數組中搜索之二)
- C++實現LeetCode(88.混合插入有序數組)