→ a9486l: 大師 02/20 10:07
→ NTHUlagka: 大師 02/20 12:46
推 idiont: 大師 02/20 12:50
35. Search Insert Position
給你一個陣列nums和一個整數target，這個陣列以升序排序，求出若我們要插入一個數字
且維持陣列升序的話要在哪個索引位置插入。
（你必須保證在 O(logn) 的時間內完成）
Example :
Input: nums = [1,3,5,6], target = 5
Output: 2
Input: nums = [1,3,5,6], target = 7
Output: 4
思路：
1.因為原陣列已經排序完而且要插入之後也是排好的，所以就使用二分搜尋找到
target的左邊界位置並返回即可。
Java Code：
--------------------------------------
class Solution {
public int searchInsert(int[] nums, int target) {
int n = nums.length;
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r)/2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return l;
}
}
--------------------------------------
--
https://i.imgur.com/uiFto42.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.18.126 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1676858164.A.982.html