每日一道算法:搜索插入位置

题目:给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例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_PHP:https://github.com/zhangdejian/LeetCode_PHP

题目来源

力扣(LeetCode):https://leetcode-cn.com/problems/search-in...

本作品采用《CC 协议》,转载必须注明作者和本文链接
阿德
zhangdeTalk
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!