闯关leetcode——35. Search Insert Position
大纲
- 题目
- 地址
- 内容
- 解题
- 代码地址
题目
地址
https://leetcode.com/problems/search-insert-position/description/
内容
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.
Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2
Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1
Example 3:
Input: nums = [1,3,5,6], target = 7
Output: 4
Constraints:
- 1 <= nums.length <= 104
- -104 <= nums[i] <= 104
- nums contains distinct values sorted in ascending order.
- -104 <= target <= 104
解题
这题要求在一个无重复的、升序数组中,寻找一个数的下标。如果该数不存在,则寻找到可以插入该数的下标。
这个算是二分查找问题的一个变种。一般情况下,我们要求二分查找算法在数据不存在的情况下,返回-1,表示没有找到。如果我们希望返回可以插入数据的位置,只需要对返回-1的地方做个修改,让其返回待插入的位置。
#include <vector>
using namespace std;class Solution {
public:int searchInsert(vector<int>& nums, int target) {int right = nums.size() - 1;return binarySearch(nums, target, 0, right);}
private:int binarySearch(const vector<int>& nums, int target, int left, int right) {if (left > right) {return left;}int mid = (left + right) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {return binarySearch(nums, target, mid + 1, right);} else {return binarySearch(nums, target, left, mid - 1);}}
};
代码地址
https://github.com/f304646673/leetcode/tree/main/35-Search-Insert-Position
原文地址:https://blog.csdn.net/breaksoftware/article/details/142070711
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mrgr.cn/news/29861.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mrgr.cn/news/29861.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!