每日一道算法:搜索插入位置
题目:给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例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
相关标签
* 数组
* 二分查找
解法一:暴力法
思路分析:
循环遍历数组,比较指针对应数组位置的值与目标值的对比,因为是已经排序好的数组,所以当出现大于等于时的指针就是结果,否则就是最大的值,数组再加一位。
PHP代码实现:
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer
*/
function searchInsert($nums, $target) {
for($i=0;$i<count($nums);$i++){
if($nums[$i] >= $target){
return $i;
}
}
return count($nums);
}
使用:
$nums = [1,3,5,6];
$target = 7;
var_dump(searchInsert($nums, $target));
复杂度分析:
时间复杂度: O(n)
最好的情况是O(1),最坏的情况是O(n)
空间复杂度: O(1)
没有额外空间被使用
当数组长度大一点时,很容易超出时间限制和溢出内存,明显是一个很粗暴的解决方法
解法二:二分查找法
思路分析:
先设定左侧下标 left 和右侧下标 right,再计算中间下标 mid,每次根据 nums[mid] 和 target 之间的大小进行判断,相等则直接返回下标,nums[mid] < target 则 left 右移,nums[mid] > target 则 right 左移,查找结束如果没有相等值则返回 left,该值为插入位置。
PHP代码实现:
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer
*/
function searchInsert($nums, $target) {
$left = 0;
$right = count($nums)-1;
while($left<=$right){
$mid = intval(($left+$right)/2);
if($nums[$mid] == $target){
return $mid;
}elseif($nums[$mid] > $target){
$right = $mid -1;
}else{
$left = $mid+1;
}
}
return $left;
}
使用:
$nums = [1,3,5,6,88,90];
$target = 100;
var_dump(searchInsert($nums, $target));
复杂度分析:
时间复杂度: O(logn)
最好的情况是O(1),最坏的情况是O(logn)
空间复杂度: O(1)
没有额外空间被使用
二分查找法是最优解法
二分查找的模板
在遇到二分查找相关的算法题,都可以套用以下模板。
/**
* 二分查找的模板
* @param Integer[] $nums
* @param Integer $target
* @return Integer
*/
function blade($nums, $target) {
$left = 0;
$right = count($nums)-1;
while($left<=$right){//注意条件界限
$mid = intval(($left+$right)/2);//注意取整
if($nums[$mid] == $target){
//相关逻辑处理;
}elseif($nums[$mid] > $target){//注意right向左偏移
$right = $mid -1;
}else{//注意left向右偏移
$left = $mid+1;
}
}
//相关值返回
return 0;
}
解题关键
在做算法题时,整理思路很重要,有时确实没特别完整的思路时,可以先动手写写,在写的过程中有时思路就会不断崩出(可能是代码感觉可以激发想法吧,哈哈)。在代码写出来之后,一定要总结规律和精简代码,因为优秀的代码都是很精简的。
github
以后每次题解都会上传到这个项目
题目来源
力扣(LeetCode):https://leetcode-cn.com/problems/search-in...
本作品采用《CC 协议》,转载必须注明作者和本文链接
推荐文章: