【JAVA】搜索插入位置——力扣每日一题（五）（2020.07.17）

「爱情、让人受尽委屈。」 2023-02-27 12:28 60阅读 0赞

### 目录 ###

*  题目：35. 搜索插入位置
 *  思路
 *   *  方法一：暴力
     *  方法二：二分法

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

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

# 题目：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.  目标值不存在于数组中，返回它将会被按顺序插入的位置。
    
    1.  普遍情况，**公式二：**`nums[pos−1] < target < nums[pos]` 返回的索引为pos\[1,n-1\]
    2.  **边界情况一**，`targer < nums[0]` 返回的索引为0
    3.  **边界情况二**，`target > nums[n-1]` 返回的索引为n

合并公式一二，可以得出我们本题的**公式三（普遍情况）**。**公式三：**`nums[pos−1] < target <= nums[pos]`  
「在一个有序数组中找第一个大于等于target 的下标」 （本题中提示：你可以假设数组中无重复元素。）  
**最终公式为**，两种边界情况+公式三  
`targer < nums[0]` 返回的索引为0  
`target > nums[n-1]` 返回的索引为n  
`nums[pos−1] < target <= nums[pos]` 返回的索引为pos\[1,n-1\]

## 方法一：暴力 ##

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)。我们只需要常数空间存放若干变量。  
    ![在这里插入图片描述][20200717174048928.png]

## 方法二：二分法 ##

**代码**

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)。我们只需要常数空间存放若干变量。  
    ![在这里插入图片描述][20200717183411180.png]

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

[Link 1]: https://blog.csdn.net/weixin_43124279
[https_zihao.blog.csdn.net]: https://zihao.blog.csdn.net/
[Link 2]: https://s1.ax1x.com/2020/06/11/tHUSvq.png
[1107710098]: https://s1.ax1x.com/2020/06/26/NroKrd.jpg
[Image 1]: 
[Python]: https://blog.csdn.net/weixin_43124279/article/details/107420394
[Link 3]: https://blog.csdn.net/weixin_43124279/category_10194088.html
[Link 4]: https://blog.csdn.net/weixin_43124279/category_10194115.html
[Link 5]: https://blog.csdn.net/weixin_43124279/category_10202733.html
[20200717174048928.png]: /images/20230209/7f5e358cbb95440bae0756da1e6f209b.png
[20200717183411180.png]: /images/20230209/67057df297b741a2999a2cc1e6b49d5d.png
[https_leetcode-cn.com_problems_search-insert-position_solution_sou-suo-cha-ru-wei-zhi-by-leetcode-solution]: https://leetcode-cn.com/problems/search-insert-position/solution/sou-suo-cha-ru-wei-zhi-by-leetcode-solution/