【leetcode刷题】T7-Search Insert Position(搜索插入位置)
【leetcode刷题】T7-Search Insert Position(搜索插入位置)
今天分享leetcode第7篇文章，也是leetcode第35题—Search Insert Position，地址是：https://leetcode.com/problems/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: 2Example 2:
Input: [1,3,5,6], 2
Output: 1【中文题目】
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2示例 2:
输入: [1,3,5,6], 2
输出: 1【思路】
在排序数组中找一个数target，如果没有就插入，这个问题等价于找到第一个大于等于target的数
我们回想数组中找一个数的方法，一般有两种：一是暴力破解，二是二分查找
因此，本题也存在两种解法：一是直接遍历数组，查找第一个大于等于target的数，时间复杂度为O(n)；二是使用“变形”的二分查找，时间复杂度为O(log(n))
什么是二分查找？
二分查找又称为折半查找，每次取中间元素与target进行比较，进而能缩小一半的查找区间（如果中间元素大于target，在左区间继续查找，反之则在右区间继续查找），常见代码是：
def binary_search(nums, target):
'''二分查找数组中存在的某个元素'''
l, r = 0, len(nums)-1
while(l <= r):
mid = (l + r) // 2
if nums[mid] == target：
return mid
# 如果中间元素大于target，在左区间继续查找
elif nums[mid] > target:
r = mid - 1
# 如果中间元素小于target，在右区间继续查找
else:
l = mid + 1需要注意的是：1）循环条件是 l <= r 2）mid元素不再考虑，使用r = mid - 1 以及l = mid + 1
二分查找变形
上面是最基础的二分查找，一般面试中会考察二分查找的变形，比如：
- 查找第一个大于target的数
- 查找第一个大于等于target的数
- 查找最后一个小于target的数
- 查找最后一个小于等于target的数
- 查找等于target的第一个数
- 查找等于target的最后一个数
- ...
头都大了，但是不用着急，不难啦~
先介绍结果：代码主体结构基本不变，仅仅改变判断条件和返回值即可
到底怎么改呢？先给个思路：使用二分查找后，l和r指向的元素有什么特点？比如下面一个伪代码：
while(l <= r):
mid = (l + r) // 2
if nums[mid] > target:
r = mid - 1
else:
l = mid + 1是不是最后nums[r]的值一定小于等于target，同时nums[l]的值一定大于target！即为：nums[r] <= target < nums[l]。那么，当需要最后一个小于等于target的元素，是不是返回r下标？当需要第一个大于target的元素，是不是返回l下标？
因此，遇到二分查找变形问题，分析问题后，直接写代码！
while(l <= r):
mid = (l + r) // 2
if nums[mid] ?? target:
r = mid - 1
else:
l = mid + 1
return ???第一个??只有>和>=两种数学逻辑符号选择，当选取>时，nums[r] <= target < nums[l]；当选取>=时，nums[r] < target <= nums[l]
第二个???一般有四种选择：r，r+1，l，l-1。根据实际情况选择即可。
以本题为例：本题抽象为查找第一个大于等于target的元素，因此我们需要nums[l] >= target，确定选择数学逻辑符号为>=，最后返回下标为l。
再举一个例子：需要选择等于target的最后一个元素，因此我们需要nums[r]<=target，确定选择数学逻辑符号为>，最后返回下标为r。
【代码】
python版本
暴力破解
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
for i in range(len(nums)):
if nums[i] >= target:
return i
# 可能数组中所有元素均小于target，应插入在数组最后
return len(nums)二分查找
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
l, r = 0, len(nums)-1
while l <= r:
mid = (l + r) // 2
# 最后nums[r] < target <= nums[l]
if nums[mid] >= target:
r = mid - 1
else:
l = mid + 1
return lC++版本
暴力破解
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int index = -1;
for(int i=0; i<nums.size(); i++){
// 该编译器不能直接返回结果，所以先存储结果，并break
if(nums[i] >= target){
index = i;
break;
}
}
if(index > -1)
return index;
// 当target大于所有数时，插入在最后
return nums.size();
}
};二分查找
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = nums.size()-1;
while(l <= r){
int mid = (l + r) / 2;
// 最后nums[r] < target <= nums[l]
if(nums[mid] >= target)
r = mid - 1;
else
l = mid + 1;
}
return l;
}
};