问题描述:
Given a sorted array 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 may assume no duplicates in the array.
Here are few examples.[1,3,5,6]
, 5 → 2[1,3,5,6]
, 2 → 1[1,3,5,6]
, 7 → 4[1,3,5,6]
, 0 → 0
原问题链接:https://leetcode.com/problems/search-insert-position/
问题分析
应该说这是二分查找方法的另一个变体。针对这个排序的数组,我们要找到一个可以插入目标元素的位置。这里可以根据几种情况来考虑。首先,数组里面没有元素。那么肯定返回的是0。另外的几种情况就是如果目标值比数组的第一个元素小,那么肯定也是返回0。而如果这个目标元素比数组的最后一个元素大,那么应该返回数组的长度值,也就是nums.length。
剩下要找目标元素的位置就应对的是常规的情况了。这个目标元素肯定在数组的中间某个位置。于是就可以用常规的二分查找。如果找到了就返回。而如果没找到呢?我们返回l的值就可以了。为什么呢?因为在循环while(l <= r)的这个循环跳出的情况下,当没有找到匹配的值时,l最终取的值是要比r大的。而在循环里所有l的取值都比目标值要小。它们最终退出时会有l == r的情况之后l = l + 1的值了。这个值比l原来的那个值要大,但是从r的取值情况来看它是正好比目标值要大的。而我们要找的就是正好在一个比目标值小和一个比目标值大的数中间。所以正好取l就可以了。
详细代码实现如下:
public class Solution { public int searchInsert(int[] nums, int target) { if(nums.length == 0 || target < nums[0]) return 0; int len = nums.length, l = 0, r = nums.length - 1; if(target > nums[len - 1]) return len; while(l <= r) { int mid = l + (r - l) / 2; if(nums[mid] == target) return mid; else if(nums[mid] < target) l = mid + 1; else r = mid - 1; } return l; } }
这方法是二分查找的简单变化,所以其时间复杂度还是一样的O(logN)。
相关推荐
leetcode 1004 leetcode E:简单,M:中等,H:困难 数组和字符串 217. Contains Duplicate (E) 48. Rotate Image (M) -> 2 73. Set Matrix Zeroes ...Search ...Position ...Search Insert Position (E)
leetcode 答案LeetCode LeetCode in Swift ...Position Easy #38 Count and Say Easy #53 Maximum Subarray Easy #66 Plus One Easy #70 Climbing Stairs Easy #83 Remove Duplicates from Sorted L
leetcode 答案 ...Position 找target能插入的第一个位置 或 比target小的值有几个 H-Index II 注意是找后面的target 而且是动态target sqrtx 答案集进行二分 找 mid <= x/mid 的最后一个值 Find Pea
leetcode 答案 #LeetCode LeetCode solution By Li Yiji. Maybe not ...每个cpp文件的文件名中前边的...Position 我图省事,直接用的遍历。正常情况下应该使用二分查找 ###031 Remove Element 我的解法不太好,而且不严密
"interleaving_string.erl","search_insert_position.erl", "three_sum.erl","trapping_rain_water.erl", "valid_palindrome.erl" 个人认为dungeon_game这个题目解题逻辑很体现erlang的函数式的思维逻辑
leetcode 316 leetcode 题解更新脚本 用于快速的更新题解、同步leetcode的做题情况。 题解见: 文件名 用途 add_to_blog_solution_table.py 添加题解地址or题解语言到表格,能同步...Position Medium -> Easy 36
leetcode 答案 LeetCode-practice 记录在leetcode练习的代码&总结 ...#35SearchInsertPosition 最佳答案未解 Git使用练习 练习下分支切换&合并 解决冲突 master&feature1 禁用fast forward --no-ff 熟悉stash
Insert Position 问题:找到 nums 数组中 target 的位置。如果不存在,返回在 nums 中插入 target 的位置。 解法:问题等价于返回第一个 >= target 的数,设置好条件即可。 36 Valid Sudoku 问题
1. Introduction 2. Array i. Remove Element ii. Remove Duplicates from Sorted Array iii....iv....v....vi....vii....viii....ix....x....xi. Search a 2D Matrix xii.... Search Insert Position xiv. Find Peak Element
圆和椭圆重叠leetcode ——#158 尖端 关心特殊情况 从不同的方向思考 简单的 大批 1.Two Sum -> 使用哈希表避免遍历列表448.查找数组中消失的所有数字-> 1.建立缓冲区来计算数字| 2.使用数组作为带符号的缓冲区118....
Search Insert Position 这道题非常简单,数组是有序数组,只需要遍历一遍数组,判断当前值是否等于target或者大于target即可返回其位置值。如果都不满足, 说明target比nums中所有数都大,直接插入数组尾部,因为...
leetcode卡Leetcode-解决方案 LeetCode DS 日常挑战的解决方案 问题陈述 1.InvertBinaryTree - 2.子序列- 3.SearchInsertPosition - 4.SortColors - 5.单号——
leetcode双人赛 leetcode-solution 闲暇之余,刷一下题,弥补...search-insert-position 最大子序和 maximum-subarray 加一 plus-one 合并两个有序数组 merge-sorted-array 杨辉三角 pascals-triangle 杨辉三角 II pa
leetcode 浇花力扣解决方案 简单的 #0001 - Two Sum #0007 - Reverse Integer #0009 - Palindrome Number #0035 - Search Insert Position #0058 - Length of Last Word #0066 - Plus One #0083 - Remove Duplicates...
(searchInsertPosition.js) 搜索 2D 矩阵 - 简单 (searchA2DMatrix.js) 搜索 2D 矩阵 ii - 中 (searchA2DMatrixII.js) 第一个错误版本 - 中等 (firstBadVersion.js) 查找峰值元素 - 中等 (findPeakElement.js) 在...
丢失的最小正整数leetcode interview-algorithm 记录前端面试算法题目详解 目录 Lost Three Nums 随机从一组数组(数组内的数据为从1到n,且n为正整数)里,删除三个数,要求找到丢失的三个数,且运行较快。...Position
PalindromeNumber 13_RomanToInteger 14_LongestCommonPrefix 20_ValidParentheses 21_MergeTwoSortedLists 26_RemoveDuplicatesFromSortedArray 27_RemoveElement 28_ImplementStrStr() 35_SearchInsertPosition ...
Practice-Leetcode ...35.Search Insert Position 二分法化简 2018/04/18: 29.Divide Two Integers 二进制累加代替除法,防止溢出 36.Valid Sudoku set去重复 2018/04/19: 038.Count and Say 递归 040.C
大批 两次求和 TwoSumII 三和 ThreeSumclosest 四和 MedianOfTwoSortedArrays 装满水的容器 RemoveDuplicates ...SearchInsertPosition 组合总和 组合求和 组合SumIII 第一次缺席正 缺少号码 陷阱雨水 J
Search Insert Position Search in Rotated Sorted Array Search in Rotated Sorted Array II Search a 2D Matrix Search a 2D Matrix II Find Minimum in Rotated Sorted Array Find Minimum in Rotated Sorted ...