[Leetcode] Search Insert Position 搜索插入位置

JeOam 发布于2019-08-14 12:41 / 1295人阅读

摘要：二分搜索法复杂度时间空间思路这是最典型的二分搜索法了。这题中，我们返回就行了，如果返回，要注意的情况。代码条件是找到了在左边在右边

Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
    [1,3,5,6], 5 → 2
    [1,3,5,6], 2 → 1
    [1,3,5,6], 7 → 4
    [1,3,5,6], 0 → 0

二分搜索法 复杂度

时间 O(logN) 空间 O(1)

思路

这是最典型的二分搜索法了。如果使用我这个二分模板是可以直接适用的，在模板中，while循环的条件是min<=max，如果target和mid指向的值相等，则返回mid，否则根据情况min = mid + 1或者max = mid - 1。这样的好处是，如果找不到该数，max是比该数小的那个数的下标，而min是比该数大的那个数的下标。这题中，我们返回min就行了，如果返回max，要注意-1的情况。

代码

    public class Solution {
        public int searchInsert(int[] nums, int target) {
            int min = 0, max = nums.length - 1;
            // 条件是min <= max
            while(min <= max){
                int mid = min + (max - min) / 2;
                // 找到了
                if(nums[mid] == target){
                    return mid;
                }
                // 在左边
                if(nums[mid] > target){
                    max = mid - 1;
                } else {
                // 在右边
                    min = mid + 1;
                }
            }
            return min;
        }
    }

2018/10

func searchInsert(nums []int, target int) int {
    min := 0
    max := len(nums) - 1
    for min <= max {
        mid := min + (max-min)/2
        fmt.Printf("min: %d, max: %d, mid: %d
", min, max, mid)
        if nums[mid] == target {
            return mid
        }
        if nums[mid] > target {
            max = mid - 1
        } else if nums[mid] < target {
            min = mid + 1
        }
    }
    fmt.Printf("min: %d, max: %d
", min, max)
    return min // nums[min] will always be larger/equal than target
}

func main() {
    nums := []int{1, 3, 5, 6}
    fmt.Println(searchInsert(nums, 2))
    //     min: 0, max: 3, mid: 1
    //  min: 0, max: 0, mid: 0
    //  min: 1, max: 0
    //  1
}

GPU云服务器云服务器 LeetCode LeetCode_String leetcode_35_SearchIn position()

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64638.html

【Leetcode刷题】第 35 题：Search Insert Position 搜索插入位置——

摘要：如果目标值不存在于数组中，返回它将会被按顺序插入的位置。因此需要关注这些测试用例，在单机上逐个测试成功后再提交。因为题目中只要求返回索引，并不要求插到数组中，所以应该说又简化了一些，是一道简单题目。争取在下一篇给出优化解法。「 Leetcode刷题」系列，仅为刷题过程中对于算法和编程的思考与记录，如果对你有帮助欢迎点赞收藏。博主也在探索刷题过程中，记录的一些知识点可能很小白，因此主...

haobowd 2019-07-31 11:17 评论0 收藏0
leetcode35 Search Insert Position

题目要求：在一个有序的数组中，找到一个目标值，返回该值得下标。若没有找到该值，则返回该值顺序插入的下标例如，[1,3,5,6], 5 → 2[1,3,5,6], 2 → 1[1,3,5,6], 7 → 4[1,3,5,6], 0 → 0 public int searchInsert(int[] nums, int target) { int index=0; ...

harriszh 2019-08-14 17:54 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
leetcode381. Insert Delete GetRandom O(1) - Duplic

摘要：题目要求设计一个数据结构，支持能够在的时间内完成对数字的插入，删除和获取随机数的操作，允许插入重复的数字，同时要求每个数字被随机获取的概率和该数字当前在数据结构中的个数成正比。网上有一些实现采用来解决，这是不合理的。此时的代码如下题目要求 Design a data structure that supports all following operations in average...

h9911 2019-08-16 15:06 评论0 收藏0
leetcode380. Insert Delete GetRandom O(1)

摘要：题目要求设计一个数据结构，使得能够在的时间复杂度中插入数字，删除数字，以及随机获取一个数字。因此，使用来查询时不可避免的。如何实现的随机查询这个其实就是强调一点，我们需要维持原有的插入顺序，从而保证各个元素等概率被随机。题目要求 Design a data structure that supports all following operations in average O(1)...

phoenixsky 2019-08-16 15:06 评论0 收藏0