Go語言題解LeetCode35搜索插入位置示例詳解
題目描述
原題鏈接 :
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）如果含有與目標值相等，則返回目標值下標，若不同，則按順序排序獲取下標
思路：采用二分搜索法的策略，獲取中間數據的大小，縮短數組的大小定位區(qū)間，如在數組中間的前一段，數組中間的后一段
獲取下標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;
}
}
總結
這種查找位置的，肯定二分法是合適的，即使不能直接套用二分法的公式，也是二分法的思想，變種。
參考
??思維導圖整理: 總結了二分查找的通用模板寫法, 徹底解決幾個易混淆問題?? - 搜索插入位置
優(yōu)先考慮邊界情況 紅藍標記解法
首先考慮target是否>=nums[numsSize-1],大于則返回numsSize，等于則返回numsSize-1;
再檢查底線，若小于等于nums[0]則返回nums[0]；
else
定義左邊界left=0，右邊界right=numsSize-1；
進入循環(huán)，縮小邊界，直到left+1=right；
若找到則直接返回，循環(huán)結束時未找到則返回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語言搜索插入位置的資料請關注腳本之家其它相關文章！
相關文章
在 Redis 中,Pipeline 就像一條流水線,它允許我們將多個命令一次性發(fā)送到服務器,下面我們就來看看如何在Go語言中高效使用Redis的Pipeline吧2024-11-11
這篇文章主要為大家詳細介紹了如何基于Go語言開發(fā)一個編解碼工具,文中的示例代碼講解詳細,具有一定的借鑒價值,感興趣的小伙伴可以跟隨小編一起了解一下2025-03-03
樹是一種重要的數據結構,而二叉搜索樹（BST）則是樹的一種常見形式,在本文中,我們將學習如何構建一個高效的二叉搜索樹聯系簿,感興趣的可以了解下2024-01-01
這篇文章主要介紹了Golang切片功能操作詳情，切片是一個擁有相同類型元素的可變長度的序列。它是基于數組類型做的一層封，切片是一個引用類型，它的內部結構包含地址、長度和容量2022-09-09
這篇文章主要為大家介紹了go-cache的基本使用場景示例解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-04-04
GoFrame?gmap遍歷hashmap?listmap?treemap使用技巧
這篇文章主要為大家介紹了GoFrame?gmap遍歷hashmap?listmap?treemap使用技巧的示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-06-06
這篇文章主要為大家詳細介紹了Golang中的HTTP編程以及源碼解析，文中的示例代碼講解詳細，具有一定的借鑒價值，感興趣的可以了解一下2023-02-02
Go 語言提供了 sync 包，其中包括 Mutex 互斥鎖、RWMutex 讀寫鎖等同步機制，本篇博客將著重介紹 Mutex 互斥鎖的基本原理，需要的可以參考一下2023-04-04
下面小編就為大家分享一篇golang實現并發(fā)數控制的方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2017-12-12
這篇文章主要為大家介紹了Go Java算法之累加數示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-08-08