赞
踩
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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
其实题目透露的 O( logn ) ,就是在明示我们用 二分查找 了,只不过这道题多了一个插入位置的实现。
而这也是不难的,因为当找不到的时候,我们返回 left 指针的后一个位置就行了。
- class Solution {
- public int searchInsert(int[] nums, int target) {
- int n = nums.length;
- int left = 0;
- int right = n - 1;
- while(left < right){
- int mid = left + (right - left) / 2;
- if(nums[mid] < target){
- left = mid + 1;
- }else{
- right = mid;
- }
- }
- if(nums[right] < target){
- return left + 1;
- }
- return right;
- }
- }
以上就是本篇博客的全部内容啦,如有不足之处,还请各位指出,期待能和各位一起进步!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。