大家好,我是代碼君,在BAT從事技術研發多年,利用工作之餘重刷leetcode,更多原創文章歡迎關注「代碼隨想錄」。
這是leetcode上第35號題目:搜索插入位置
給定一個排序數組和一個目標值,在數組中找到目標值,並返回其索引。如果目標值不存在於數組中,返回它將會被按順序插入的位置。
你可以假設數組中無重複元素。
示例 1:
輸入: [1,3,5,6], 5
輸出: 2
示例 2:
輸入: [1,3,5,6], 2
輸出: 1
示例 3:
輸入: [1,3,5,6], 7
輸出: 4
示例 4:
輸入: [1,3,5,6], 0
輸出: 0
思路:
這道題目其實是一道很簡單的題,但是為什麼通過率相對來說並不高呢,我理解是大家對 邊界處理的判斷有所失誤,導致的。
我這裡給出簡潔的暴力枚舉的方式,暴力解題 不一定時間消耗就非常高,關鍵看實現的方式,就像是二分查找時間消耗不一定就很低,是一樣的。
我的暴力解法效率如下:
代碼如下:
<code>class Solution {
public:
int searchInsert(vector& nums, int target) {
for (int i = 0; i < nums.size(); i++) {
if (nums[i] >= target) { // 一旦發現大於或者等於target的num[i],那麼i就是我們要的結果
return i;
}
}
return nums.size(); // 如果target是最大的,或者 nums為空,則返回nums的長度
}
};
/<code>