資訊專欄INFORMATION COLUMN
Leetcode[35] Search Insert Position
Given a sorted array and a target value, return the index if theBinary Search
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.
Example 1:
Input: [1,3,5,6], 5 Output: 2 Example 2:
Input: [1,3,5,6], 2 Output: 1 Example 3:
Input: [1,3,5,6], 7 Output: 4 Example 1:
Input: [1,3,5,6], 0 Output: 0
復(fù)雜度
O(lgN)
思路
二分法的模板：
while(left <= right) {
int mid = (left + right) / 2;
if(nums[mid] == target) return mid;
// search in the right part;
if(nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
代碼
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = (left + right) / 2;
if(nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/68356.html
題目要求：在一個有序的數(shù)組中，找到一個目標(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; ...
摘要：如果目標(biāo)值不存在于數(shù)組中，返回它將會被按順序插入的位置。因此需要關(guān)注這些測試用例，在單機(jī)上逐個測試成功后再提交。因為題目中只要求返回索引，并不要求插到數(shù)組中，所以應(yīng)該說又簡化了一些，是一道簡單題目。爭取在下一篇給出優(yōu)化解法。 「 Leetcode刷題 」系列，僅為刷題過程中對于算法和編程的思考與記錄，如果對你有幫助歡迎點贊收藏。博主也在探索刷題過程中，記錄的一些知識點可能很小白，因此主...
摘要：二分搜索法復(fù)雜度時間空間思路這是最典型的二分搜索法了。這題中，我們返回就行了，如果返回，要注意的情況。代碼條件是找到了在左邊在右邊 Search Insert Position Given a sorted array and a target value, return the index if the target is found. If not, return the inde...
Problem 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 a...
摘要：自己沒事刷的一些的題目，若有更好的解法，希望能夠一起探討項目地址 自己沒事刷的一些LeetCode的題目，若有更好的解法，希望能夠一起探討 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...
閱讀 1965·2023-04-25 15:45
閱讀 1197·2021-09-29 09:34
閱讀 2498·2021-09-03 10:30
閱讀 2000·2019-08-30 15:56
閱讀 1456·2019-08-29 15:31
閱讀 1268·2019-08-29 15:29
閱讀 3196·2019-08-29 11:24
閱讀 3048·2019-08-26 13:45
