資訊專欄INFORMATION COLUMN
摘要：二分搜索法復(fù)雜度時(shí)間空間思路這是最典型的二分搜索法了。這題中，我們返回就行了，如果返回，要注意的情況。代碼條件是找到了在左邊在右邊
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
二分搜索法
復(fù)雜度
時(shí)間 O(logN) 空間 O(1)
思路這是最典型的二分搜索法了。如果使用我這個(gè)二分模板是可以直接適用的，在模板中，while循環(huán)的條件是min<=max，如果target和mid指向的值相等，則返回mid，否則根據(jù)情況min = mid + 1或者max = mid - 1。這樣的好處是，如果找不到該數(shù)，max是比該數(shù)小的那個(gè)數(shù)的下標(biāo)，而min是比該數(shù)大的那個(gè)數(shù)的下標(biāo)。這題中，我們返回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
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64638.html
摘要：如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。因此需要關(guān)注這些測(cè)試用例，在單機(jī)上逐個(gè)測(cè)試成功后再提交。因?yàn)轭}目中只要求返回索引，并不要求插到數(shù)組中，所以應(yīng)該說又簡(jiǎn)化了一些，是一道簡(jiǎn)單題目。爭(zhēng)取在下一篇給出優(yōu)化解法。 「 Leetcode刷題 」系列，僅為刷題過程中對(duì)于算法和編程的思考與記錄，如果對(duì)你有幫助歡迎點(diǎn)贊收藏。博主也在探索刷題過程中，記錄的一些知識(shí)點(diǎn)可能很小白，因此主...
題目要求：在一個(gè)有序的數(shù)組中，找到一個(gè)目標(biāo)值，返回該值得下標(biāo)。若沒有找到該值，則返回該值順序插入的下標(biāo)例如，[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; ...
摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
摘要：題目要求設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)，支持能夠在的時(shí)間內(nèi)完成對(duì)數(shù)字的插入，刪除和獲取隨機(jī)數(shù)的操作，允許插入重復(fù)的數(shù)字，同時(shí)要求每個(gè)數(shù)字被隨機(jī)獲取的概率和該數(shù)字當(dāng)前在數(shù)據(jù)結(jié)構(gòu)中的個(gè)數(shù)成正比。網(wǎng)上有一些實(shí)現(xiàn)采用來解決，這是不合理的。此時(shí)的代碼如下 題目要求 Design a data structure that supports all following operations in average...
摘要：題目要求設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)，使得能夠在的時(shí)間復(fù)雜度中插入數(shù)字，刪除數(shù)字，以及隨機(jī)獲取一個(gè)數(shù)字。因此，使用來查詢時(shí)不可避免的。如何實(shí)現(xiàn)的隨機(jī)查詢這個(gè)其實(shí)就是強(qiáng)調(diào)一點(diǎn)，我們需要維持原有的插入順序，從而保證各個(gè)元素等概率被隨機(jī)。 題目要求 Design a data structure that supports all following operations in average O(1)...
閱讀 2152·2023-05-11 16:55
閱讀 3516·2021-08-10 09:43
閱讀 2631·2019-08-30 15:44
閱讀 2452·2019-08-29 16:39
閱讀 593·2019-08-29 13:46
閱讀 2015·2019-08-29 13:29
閱讀 931·2019-08-29 13:05
閱讀 702·2019-08-26 13:51
