大佬教程收集整理的这篇文章主要介绍了35. (Search Insert Position)搜索插入位置,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
Given a sorted array of disTinct Integers 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 must write an algorithm with O(log n) runtime complexity.
给定一个排序数组和一个目标值c;在数组中找到目标值c;并返回其索引。如果目标值不存在于数组中c;返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
Example 1:
Input: nums = [1,3,5,6], target = 5 Output: 2
示例 1:
输入: nums = [1,3,5,6], target = 5 输出: 2
Example 2:
Input: nums = [1,3,5,6], target = 2 Output: 1
示例 2:
输入: nums = [1,3,5,6], target = 2 输出: 1
Example 3:
Input: nums = [1,3,5,6], target = 7 Output: 4
示例 3:
输入: nums = [1,3,5,6], target = 7 输出: 4
Example 4:
Input: nums = [1,3,5,6], target = 0 Output: 0
示例 4:
输入: nums = [1,3,5,6], target = 0 输出: 0
Example 5:
Input: nums = [1], target = 0 Output: 0
示例 5:
输入: nums = [1], target = 0 输出: 0
ConsTraints:
提示:
方法:二分查找
当题目中只要求我们找到一个排序数组中的一个目标值并返回其索引值时c;我们第一想到的就是二分查找。然而题目中还有一个条件当这个目标值不在时c;返回按顺序插入的索引值。
我们使用position来定义插入的位置时: 满足条件nums[positon-1] < < < target ≤ leq ≤ nums[position](即在一个有序数组中找第一个大于target值的索引值c;返回按顺序插入的索引值。
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums)-1
while(left <= right):
mid = left + (right - left) // 2
if (nums[@H_967_114@mid] < target):
left = mid + 1
elif (nums[@H_967_114@mid] > target):
right = mid - 1
else :
return mid
return left
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[@H_967_114@mid] < target) {
left = mid + 1;
} else if(nums[@H_967_114@mid] > target) {
right = mid - 1;
} else {
return mid;
}
}
return left;
}
}
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int n = nums.size();
int left = 0,right = n-1;
while(left <= right){
int mid = left + (right - left) / 2;
if(target <= nums[@H_967_114@mid]){
right = mid - 1;
}
else{
left = mid + 1;
}
}
return left;
}
};
时间复杂度:O( l o g n log_n logn)c;其中 n为数组的长度。二分查找所需的时间复杂度为 O( l o g n log_n logn)。
空间复杂度:O(1)。我们只存放若干变量。
以上是大佬教程为你收集整理的35. (Search Insert Position)搜索插入位置全部内容,希望文章能够帮你解决35. (Search Insert Position)搜索插入位置所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。