弄一个关于作文的网站怎么做,wordpress短代码教程,网站做动态虚线,怎么关注网站 在手机上给定一个排序数组和一个目标值#xff0c;在数组中找到目标值#xff0c;并返回其索引。如果目标值不存在于数组中#xff0c;返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums [1,3,5,6], target 5 输出: 2 示例 2:
输入…给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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 104 -104 nums[i] 104 nums 为 无重复元素 的 升序 排列数组 -104 target 104
直接二分搜索即可
func searchInsert(nums []int, target int) int {left : 0right : len(nums) - 1res : len(nums)for left right {mid : int(left (right - left) / 2)if nums[mid] target {res midright mid - 1} else if nums[mid] target {left mid 1}}return res
}C解法
class Solution {
public:int searchInsert(vectorint nums, int target) {int left 0;int right nums.size() - 1;int res nums.size();while (left right) {int mid left ((right - left) 1);if (nums[mid] target){res mid;right mid - 1;}else{left mid 1;}}return res;}
};此算法时间复杂度为O(logn)空间复杂度为O(1)。
