Search Insert Position
来自 <https://leetcode.com/problems/search-insert-position/>
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
题目解读
给定一个有序数组和一个特定的target值,如果数组中存在target,返回其在数组中的index,如果没找到,返回其插入点的位置,使该数组称为一个有序数组。
数组中的所有数都不是重复的。
例子
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
解析:
解法一:最简单的方法就是从前向后遍历,找到与target相等或者比target大但相差最小的元素的index,将index返回。
解法二:利用二分查找,找到插入点的位置。
解法一Java代码:
public class Solution { public int searchInsert(int[] nums, int target) { for(int i=0; i<nums.length; i++) { if(target == nums[i] || target < nums[i]) return i; else { if(i<nums.length-1) { continue; } else { return nums.length; } } } return nums.length; } }
解法一性能
解法二代码
public class Solution { /** * 二分查找 * @param nums * @param target * @return */ public int searchInsert(int[] nums, int target) { if(nums == null) return 0; int low = 0; int high = nums.length-1; int mid = 0;; while(low < high) { mid = (low + high) / 2; if(nums[mid] == target) return mid; else if(nums[mid] > target) high = mid-1; else low = mid+1; } if(nums[low] >= target) return low; else return low+1; } }
解法二性能
相关推荐
leetcode双人赛 leetcode-solution 闲暇之余,刷一下题,弥补...search-insert-position 最大子序和 maximum-subarray 加一 plus-one 合并两个有序数组 merge-sorted-array 杨辉三角 pascals-triangle 杨辉三角 II pa
leetcode卡Leetcode-解决方案 LeetCode DS 日常挑战的解决方案 问题陈述 1.InvertBinaryTree - 2.子序列- 3.SearchInsertPosition - 4.SortColors - 5.单号——
leetcode 答案 LeetCode-practice 记录在leetcode练习的代码&总结 ...#35SearchInsertPosition 最佳答案未解 Git使用练习 练习下分支切换&合并 解决冲突 master&feature1 禁用fast forward --no-ff 熟悉stash
PalindromeNumber 13_RomanToInteger 14_LongestCommonPrefix 20_ValidParentheses 21_MergeTwoSortedLists 26_RemoveDuplicatesFromSortedArray 27_RemoveElement 28_ImplementStrStr() 35_SearchInsertPosition ...
输入数组已排序:使用排序数组的条件,使用前后两个指针35.Search Insert Position -> 线性搜索/二分搜索(左右各有1个间隙) 66.Plus One -> 了解加法过程122.Best Time to Buy and Sell Stock II -> 动态规划 -> ...
丢失的最小正整数leetcode interview-algorithm 记录前端面试算法题目详解 目录 Lost Three Nums 随机从一组数组(数组内的数据为从1到n,且n为正整数)里,删除三个数,要求找到丢失的三个数,且运行较快。...Position
leetcode 316 leetcode 题解更新脚本 用于快速的更新题解、同步leetcode的做题情况。 题解见: 文件名 用途 add_to_blog_solution_table.py 添加题解地址or题解语言到表格,能同步...Position Medium -> Easy 36
leetcode 答案 ...Position 找target能插入的第一个位置 或 比target小的值有几个 H-Index II 注意是找后面的target 而且是动态target sqrtx 答案集进行二分 找 mid <= x/mid 的最后一个值 Find Pea
leetcode 1004 leetcode E:简单,M:中等,H:困难 数组和字符串 217. Contains Duplicate (E) 48. Rotate Image (M) -> 2 73. Set Matrix Zeroes ...Search ...Position ...35. 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 浇花力扣解决方案 简单的 #0001 - Two Sum #0007 - Reverse Integer #0009 - Palindrome Number #0035 - Search Insert Position #0058 - Length of Last Word #0066 - Plus One #0083 - Remove Duplicates...
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的函数式的思维逻辑
##NO.35 Search Insert Position 这道题非常简单,数组是有序数组,只需要遍历一遍数组,判断当前值是否等于target或者大于target即可返回其位置值。如果都不满足, 说明target比nums中所有数都大,直接插入数组尾部...
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
Insert Position 问题:找到 nums 数组中 target 的位置。如果不存在,返回在 nums 中插入 target 的位置。 解法:问题等价于返回第一个 >= target 的数,设置好条件即可。 36 Valid Sudoku 问题
(searchInsertPosition.js) 搜索 2D 矩阵 - 简单 (searchA2DMatrix.js) 搜索 2D 矩阵 ii - 中 (searchA2DMatrixII.js) 第一个错误版本 - 中等 (firstBadVersion.js) 查找峰值元素 - 中等 (findPeakElement.js) 在...
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
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 ...
大批 两次求和 TwoSumII 三和 ThreeSumclosest 四和 MedianOfTwoSortedArrays 装满水的容器 RemoveDuplicates ...SearchInsertPosition 组合总和 组合求和 组合SumIII 第一次缺席正 缺少号码 陷阱雨水 J