LeetCode 每日一题「搜索插入位置」

我是陈皮，一个在互联网 Coding 的 ITer，微信搜索「陈皮的JavaLib」第一时间阅读最新文章，回复【资料】，即可获得我精心整理的技术资料，电子书籍，一线大厂面试资料和优秀简历模板。

题目

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

必须使用时间复杂度为 O(logn) 的算法。

示例 1:

• 输入: nums = [1,3,5,6], target = 5
• 输出: 2

示例 2:

• 输入: nums = [1,3,5,6], target = 2
• 输出: 1

示例 3:

• 输入: nums = [1,3,5,6], target = 7
• 输出: 4

示例 4:

• 输入: nums = [1,3,5,6], target = 0
• 输出: 0

示例 5:

• 输入: nums = [1], target = 0
• 输出: 0

提示:

• 1 <= nums.length <= 10^4^
• -10^4^ <= nums[i] <= 10^4^
• nums 为无重复元素的升序排列数组
• -10^4^ <= target <= 10^4^

分析

从题目分析有几个关键点，综合分析使用二分查找法最合适。

• 升序排序的数组
• 元素无重复
• 数组至少有一个元素，最多1000个元素
• 时间复杂度必须要 O(logn)

暴力法

抛开算法性能要求，每一种问题都会有暴力的解决方法，也就是我们常人最容易想到的方法，那就是从头到尾遍历数组中的所有元素，直到找到大于或等于待查找值的元素。

package com.chenpi;

/**
 * @Description 35. 搜索插入位置
 * @Author 陈皮
 * @Date 2021/8/30
 * @Version 1.0
 */
public class SearchInsert {

    public int searchInsert(int[] nums, int target) {
        // 从头到尾遍历所有元素
        for (int i = 0; i < nums.length; i++) {

            if (nums[i] >= target) {
                // 找到目标值，或者找到第一个大于目标值的元素，则返回下标
                return i;
            }
        }
        // 没有找到目标值，并且目标值都比数组中元素值大，则插入到数组最后
        return nums.length;
    }

    public static void main(String[] args) {
        SearchInsert inst = new SearchInsert();
        int[] nums = {1, 3, 5, 6};
        System.out.println(inst.searchInsert(nums, 5));
    }
}

二分法

系统要求时间复杂度必须要 O(logn)，数组又是有序的，那最合适的就是使用二分查找法。

package com.chenpi;

/**
 * @Description 35. 搜索插入位置
 * @Author 陈皮
 * @Date 2021/8/30
 * @Version 1.0
 */
public class SearchInsert {

    public int searchInsert(int[] nums, int target) {

        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {

            // 找出中间位置，使用此方法可以防止溢出，等同(left + right)/2
            int middle = left + ((right - left) / 2);

            if (nums[middle] > target) {
                // 目标值在左区间
                right = middle - 1;
            } else if (nums[middle] < target) {
                // 目标值在右区间
                left = middle + 1;
            } else {
                // 找到目标值
                return middle;
            }
        }
        return right + 1;
    }

    public static void main(String[] args) {
        SearchInsert inst = new SearchInsert();
        int[] nums = {1, 3, 5, 6};
        System.out.println(inst.searchInsert(nums, 5));
    }
}

本次分享到此结束啦~~

如果觉得文章对你有帮助，点赞、收藏、关注、评论，您的支持就是我创作最大的动力！