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

Posted on by

題目描述

原題鏈接 :

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

給定一個排序數組和一個目標值，在數組中找到目標值，並返回其索引。如果目標值不存在於數組中，返回它將會被按順序插入的位置。

請必須使用時間復雜度為 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 為 無重復元素 的 升序 排列數組

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

思路分析

首先明確題目的含義：

（1）數組是有序的；

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

思路：采用二分搜索法的策略，獲取中間數據的大小，縮短數組的大小定位區間，如在數組中間的前一段，數組中間的後一段

獲取下標i的值arrs[i]>=target,進行相應的下標返回

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;
    }
}

總結

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

參考

❤️思維導圖整理: 總結瞭二分查找的通用模板寫法, 徹底解決幾個易混淆問題❤️ – 搜索插入位置

優先考慮邊界情況 紅藍標記解法

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

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

else

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

進入循環，縮小邊界，直到left+1=right；

若找到則直接返回，循環結束時未找到則返回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搜索插入位置示例詳解的詳細內容，更多關於Go語言搜索插入位置的資料請關註WalkonNet其它相關文章！

推薦閱讀：