Go語言題解LeetCode35搜索插入位置示例詳解

更新時(shí)間：2022年12月30日 15:15:16 作者：劉09k11

這篇文章主要為大家介紹了Go語言題解LeetCode35搜索插入位置示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目描述

原題鏈接 :

35. 搜索插入位置 - 力扣（LeetCode） (leetcode-cn.com)

給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。

請(qǐng)必須使用時(shí)間復(fù)雜度為 O(log n) 的算法。

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

提示:

1 <= nums.length <= 10^4

-10^4 <= nums[i] <= 10^4

nums 為無重復(fù)元素的升序排列數(shù)組

-10^4 <= target <= 10^4

思路分析

首先明確題目的含義：

（1）數(shù)組是有序的；

（2）如果含有與目標(biāo)值相等，則返回目標(biāo)值下標(biāo)，若不同，則按順序排序獲取下標(biāo)

思路：采用二分搜索法的策略，獲取中間數(shù)據(jù)的大小，縮短數(shù)組的大小定位區(qū)間，如在數(shù)組中間的前一段，數(shù)組中間的后一段

獲取下標(biāo)i的值arrs[i]>=target,進(jìn)行相應(yīng)的下標(biāo)返回

AC 代碼

class Solution {
    public int searchInsert(int[] nums, int target) {
        int index = (nums.length / 2);
        if (nums[index] >= target) {
            return compareByIndex(nums, 0, index+1, target);
        } else
            return compareByIndex(nums, index+1, nums.length, target);
    }
    private int compareByIndex(int[] nums, int start, int end, int target) {
        for (int i = start; i < end; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        return end;
    }
}

總結(jié)

這種查找位置的，肯定二分法是合適的，即使不能直接套用二分法的公式，也是二分法的思想，變種。

參考

??思維導(dǎo)圖整理: 總結(jié)了二分查找的通用模板寫法, 徹底解決幾個(gè)易混淆問題?? - 搜索插入位置

優(yōu)先考慮邊界情況紅藍(lán)標(biāo)記解法

首先考慮target是否>=nums[numsSize-1],大于則返回numsSize，等于則返回numsSize-1;

再檢查底線，若小于等于nums[0]則返回nums[0]；

else

定義左邊界left=0，右邊界right=numsSize-1；

進(jìn)入循環(huán)，縮小邊界，直到left+1=right；

若找到則直接返回，循環(huán)結(jié)束時(shí)未找到則返回left+1（在left與right之間）

代碼

int searchInsert(int* nums, int numsSize, int target){
    if(nums[0]>=target)
    {
        return 0;
    }
    else if(nums[numsSize-1]<target)
    {
         return numsSize;
    }
    else if(nums[numsSize-1]==target)
    {
        return numsSize-1;
    }
    else{
         int r=numsSize-1;
         int i=0;
    while(i+1!=r)
    {
        int mid=(i+r)/2;
    if(nums[mid]>target )
{
    r=mid;
}
        else if(nums[mid]<target)
                 i=mid;
        else{
                 return mid;
 }
    }
            return i+1;

    }
}

以上就是Go語言題解LeetCode35搜索插入位置示例詳解的詳細(xì)內(nèi)容，更多關(guān)于Go語言搜索插入位置的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: