做门票售卖网站,怎么制作自己的水印,怎么搞免费的网站,公司网页设计推广服务公司力扣#xff1a;35. 搜索插入位置
描述
给定一个排序数组和一个目标值#xff0c;在数组中找到目标值#xff0c;并返回其索引。如果目标值不存在于数组中#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1:
输入: nums [1,…力扣35. 搜索插入位置
描述
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1:
输入: nums [1,3,5,6], target 5 输出: 2 示例 2:
输入: nums [1,3,5,6], target 2 输出: 1 示例 3:
输入: nums [1,3,5,6], target 7 输出: 4
提示:
1 nums.length 104 -104 nums[i] 104 nums 为 无重复元素 的 升序 排列数组 -104 target 104
1.暴力解法
从数组的左边遍历到右边如果遇到相等的元素直接返回下标如果遇到第 1 个严格大于 target 的元素返回这个元素的下标如果数组里所有的元素都严格小于 target返回数组的长度 len。 代码如下
#includeiostream
#includevector
using namespace std;
class Solution{
public:int searchInsert(vectorint nums, int target){int num 0;int tmp 0;for(int i 0; i nums.size(); i){if(nums[i] target){return i;}if(nums[i] target num 0){tmp i;num 1;}}if(num 0){return nums.size();}else {return tmp;}}
};int main(){Solution solution;vectorint nums {1,3,5,6,9,13,27,34,49,58,60};int target 44;int insertPostion solution.searchInsert(nums,target);cout The inset postion for target target is insertPostion endl;return 0;
}{int len nums.size();if(len 0){return 0;}if(nums[len - 1] target){return len;}int left 0;int right len - 1;while(left right){int mid left ((right - left) / 2);if(nums[mid] target){left mid 1;}else {right mid;}}return left;}
};
int main()
{Solution solution;vectorint nums {1,3,5,6,9,13,27,34,49,58,60};int target 44;int insertPostion solution.insearchInsert(nums,target);cout The target target is insertPostion endl;return 0;
}时间复杂度O(logn)O(\log n)O(logn)其中 nnn 为数组的长度。二分查找所需的时间复杂度为 O(logn)O(\log n)O(logn)。
空间复杂度O(1)O(1)O(1)。我们只需要常数空间存放若干变量。
力扣35. 搜索插入位置
