【JAVA数据结构算法】搜索插入位置

如果你从本文中学习到丝毫知识，那么请您点点关注、点赞、评论和收藏
大家好，我是爱做梦的鱼，我是东北大学大数据实验班大三的小菜鸡，非常渴望优秀，羡慕优秀的人，个人博客为：爱做梦的鱼https://zihao.blog.csdn.net/，微信公众号、微信视频号为【程序猿干货铺】

如果你同样热爱算法，那么请关注我，我将每日更新力扣的每日一题的题解+代码，每周更新力扣周赛题解+代码
《本题Python代码版》
专栏《力扣每日一题》
专栏《力扣周赛》
专栏《力扣大厂模拟面试算法题》

题目：35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。

示例 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

思路

本题需要考虑两种情况

1. 目标值存在，返回其索引。
   公式一：target = nums[pos]
2. 目标值不存在于数组中，返回它将会被按顺序插入的位置。
   公式二：nums[pos−1] < target < nums[pos]

合并公式一二，可以得出我们本题的最终公式。「在一个有序数组中找第一个大于等于target 的下标」 （本题中提示：你可以假设数组中无重复元素。）
公式三：nums[pos−1] < target <= nums[pos]

方法一：暴力

public class SearchInsertPosition {
    public static void main(String[] args) {
        int[] a = {1, 3, 5, 6};
        System.out.println(new Solution().searchInsert(a, 5));
        System.out.println(new Solution().searchInsert(a, 1));
        System.out.println(new Solution().searchInsert(a, 6));
    }
}

//代码未简化
public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        //先考虑边界情况，返回值最左边：0；最右边：n；
        //一、最左边边界情况：返回值为0  {1, 3, 5, 6}，0
        if (target <= nums[0])
            return 0;
        //二、最右边边界情况：返回值为0  {1, 3, 5, 6}，7
        if (target > nums[n - 1])
            return n;
        //三、后考虑普遍情况，返回值1 ~ n-1 {1, 3, 5, 6}，5
        for (int i = 1; i < n; i++)
            if (target > nums[i - 1] && target <= nums[i])
                return i;
        return -1;
    }

简化代码

//简化的代码
    public int searchInsert(int[] nums, int target) {
        //将最左边边界情况和普遍情况合并
        for (int i = 0; i < nums.length; i++)
            if (target <= nums[i])
                return i;
        return nums.length;  //返回的是最右边边界情况
    }

复杂度分析

• 时间复杂度：O(n)，其中 n 为数组的长度。

• 空间复杂度：O(1)。我们只需要常数空间存放若干变量。
  

方法二：二分法

代码

public class SearchInsertPosition2 {
    public static void main(String[] args) {
        int[] a = {1, 3, 5, 6};
        System.out.println(new SearchInsertPosition2().searchInsert(a, 5));
        System.out.println(new SearchInsertPosition2().searchInsert(a, 1));
        System.out.println(new SearchInsertPosition2().searchInsert(a, 7));
    }

    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int left = 0;
        int right = n - 1;
        int ans = n; //ans 初值设置为数组长度可以省略边界条件的判断，因为存在一种情况是 target 大于数组中的所有数，此时需要插入到数组长度的位置。
        while (left <= right) {
            int middle = (left + right) / 2;
            if (target <= nums[middle]) {
                ans = middle;
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(logn)，其中 n 为数组的长度。二分查找所需的时间复杂度为 O(logn)。

• 空间复杂度：O(1)。我们只需要常数空间存放若干变量。
  

建议大家去看力扣官方讲解
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/search-insert-position/solution/sou-suo-cha-ru-wei-zhi-by-leetcode-solution/
来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

本文地址：https://blog.csdn.net/weixin_43124279/article/details/107415356