Go語言題解LeetCode35搜尋插入位置範例詳解

2022-12-31 14:01:36

題目描述

原題連結 :

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語言搜尋插入位置的資料請關注it145.com其它相關文章！