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

JeOam 發布于2019-08-14 12:41 / 1316人閱讀

摘要：二分搜索法復雜度時間空間思路這是最典型的二分搜索法了。這題中，我們返回就行了，如果返回，要注意的情況。代碼條件是找到了在左邊在右邊

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()

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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