美文网首页程序员
【算法】LeetCode算法题-Search Insert Po

【算法】LeetCode算法题-Search Insert Po

作者: 程序员小川 | 来源:发表于2018-10-26 08:13 被阅读1次

    这是悦乐书的第152次更新,第154篇原创

    01 看题和准备

    今天介绍的是LeetCode算法题中Easy级别的第11题(顺位题号是35)。给定排序数组和目标值,如果找到目标,则返回索引。 如果没有,请返回索引按顺序插入的索引。假设数组中没有重复项。例如:

    输入:[1,3,5,6],5
    输出:2

    输入:[1,3,5,6],2
    输出:1

    输入:[1,3,5,6],7
    输出:4

    输入:[1,3,5,6],0
    输出:0

    本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

    02 第一种解法

    首先排除几种特殊情况,然后顺位循环,拿每一个元素与目标值比较。

    public int searchInsert(int[] nums, int target) {
        if (nums.length == 0 || nums[0] > target) { 
            return 0;
        }
        if(nums[nums.length-1] < target){ 
            return nums.length;
        }
        int result = 0;
        for(int i=0; i<nums.length; i++){
            if (nums[i] < target) {
                result++;
            }
            if (nums[i] == target) {
                return i;
            }
        }
        return result;
    }
    

    03 第二种解法

    使用二分法快速定位,取中间位索引判断值,直到匹配上。

    public int searchInsert2(int[] nums, int target) {
        int L = 0;
        int R = nums.length-1;
        while (true) {
            if (target <= nums[L]) {
                return L;
            }
            if (target > nums[R]) {
                return R+1;
            }
            int mid = (L+R)/2;
            if (target <= nums[mid]) {
                R = mid-1;
            }
            if (target > nums[mid]) {
                L = mid+1;
            }
        }
    }
    

    04 小结

    以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

    相关文章

      网友评论

        本文标题:【算法】LeetCode算法题-Search Insert Po

        本文链接:https://www.haomeiwen.com/subject/mqahtqtx.html