【Leetcode刷题】搜索插入位置
文章目录
- 一、题目链接
- 二、思路
- 三、题解
- 题解一（暴力法）
- 题解二（二分法）
一、题目链接
Leetcode链接：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. 目标值不在数组中，但比数组中的元素都要小
例如：
这时目标值将会插入0的位置，所以返回下标0
2. 目标值等于数组中的一个元素
例如：
这时，我们只需返回3的下标
3. 目标值不在数组中，但比数组中的某个元素大，又比某个元素小 – 即目标值将会插入数组中的位置
例如：
这时，目标值将会插入2的位置，所以返回下标2
4. 目标值不在数组中，但比数组中所有元素都大。
例如：
这时，目标值将会插入数组最后一个位置的下一个位置，返回4。
三、题解
题解一（暴力法）
思路：
遍历数组，找到第一个比target大的数，它的位置就是目标值将会插入的位置，所以返回它的下标。若target比所有数都大，则返会数组的大小。
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();
}
};
时间复杂度O(N)
由于题目要求必须时间复杂度为O(logN),所以请看下面一种方法
题解二（二分法）
思路：
由于题目中出现排序数组并且无重复元素，所以我们可以考虑是否能用二分法
若目标值在数组中，利用二分法查找目标值，这一种情况就不再多说了，若有不了解，请点击此处，进行查看，我们主要看其他三种情况
从上面三种情况的例图来看，除了在数组中的元素外，其他三种情况只需返回 右下标+1 的位置即可
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while(left <= right)
{
int mid = (left + right) / 2;//中间元素下标
if(nums[mid] > target)
right = mid - 1;
else if(nums[mid] < target)
left = mid + 1;
else
// nums[mid] == target
return mid;//等于数组中的元素时，返回下标
}
return right + 1;//除在数组中的元素外的其他三种情况
}
};