【题目】
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
【分析】
这道题比较简单,就是二分查找。思路就是每次取中间,如果等于目标即返回,否则根据大小关系切去一半。因此算法复杂度是O(logn),空间复杂度O(1)。
【代码】
/*********************************
* 日期:2015-01-24
* 作者:SJF0115
* 题目: 35.Search Insert Position
* 网址:https://oj.leetcode.com/problems/search-insert-position/
* 结果:AC
* 来源:LeetCode
* 博客:
**********************************/
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int searchInsert(int A[], int n, int target) {
if(n <= 0){
return -1;
}//if
int start = 0,end = n - 1;
// 二分查找
while(start <= end){
int mid = start + ((end - start) >> 1);
// 目标找到
if(A[mid] == target){
return mid;
}//if
// 目标在左半部分
else if(A[mid] > target){
end = mid - 1;
}//else
// 目标在右半部分
else{
start = mid + 1;
}//else
}//while
// 目标元素没有找到则找插入位置
return start;// end + 1
}
};
int main(){
Solution solution;
int A[] = {1,3,5,6};
int n = 4;
int target = 0;
int result = solution.searchInsert(A,n,target);
// 输出
cout<<result<<endl;
return 0;
}
分享到:
相关推荐
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 316 leetcode 题解更新脚本 用于快速的更新题解、同步leetcode的做题情况。 题解见: 文件名 用途 add_to_blog_solution_table.py 添加题解地址or题解语言到表格,能同步...Position Medium -> Easy 36
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)
输入数组已排序:使用排序数组的条件,使用前后两个指针35.Search Insert Position -> 线性搜索/二分搜索(左右各有1个间隙) 66.Plus One -> 了解加法过程122.Best Time to Buy and Sell Stock II -> 动态规划 -> ...
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
"interleaving_string.erl","search_insert_position.erl", "three_sum.erl","trapping_rain_water.erl", "valid_palindrome.erl" 个人认为dungeon_game这个题目解题逻辑很体现erlang的函数式的思维逻辑
leetcode卡Leetcode-解决方案 LeetCode DS 日常挑战的解决方案 问题陈述 1.InvertBinaryTree - 2.子序列- 3.SearchInsertPosition - 4.SortColors - 5.单号——
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 答案 LeetCode-practice 记录在leetcode练习的代码&总结 ...#35SearchInsertPosition 最佳答案未解 Git使用练习 练习下分支切换&合并 解决冲突 master&feature1 禁用fast forward --no-ff 熟悉stash
Insert Position 问题:找到 nums 数组中 target 的位置。如果不存在,返回在 nums 中插入 target 的位置。 解法:问题等价于返回第一个 >= target 的数,设置好条件即可。 36 Valid Sudoku 问题
##NO.35 Search Insert Position 这道题非常简单,数组是有序数组,只需要遍历一遍数组,判断当前值是否等于target或者大于target即可返回其位置值。如果都不满足, 说明target比nums中所有数都大,直接插入数组尾部...
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 我的解法不太好,而且不严密
(searchInsertPosition.js) 搜索 2D 矩阵 - 简单 (searchA2DMatrix.js) 搜索 2D 矩阵 ii - 中 (searchA2DMatrixII.js) 第一个错误版本 - 中等 (firstBadVersion.js) 查找峰值元素 - 中等 (findPeakElement.js) 在...
PalindromeNumber 13_RomanToInteger 14_LongestCommonPrefix 20_ValidParentheses 21_MergeTwoSortedLists 26_RemoveDuplicatesFromSortedArray 27_RemoveElement 28_ImplementStrStr() 35_SearchInsertPosition ...
丢失的最小正整数leetcode interview-algorithm 记录前端面试算法题目详解 目录 Lost Three Nums 随机从一组数组(数组内的数据为从1到n,且n为正整数)里,删除三个数,要求找到丢失的三个数,且运行较快。...Position
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-solution 闲暇之余,刷一下题,弥补...search-insert-position 最大子序和 maximum-subarray 加一 plus-one 合并两个有序数组 merge-sorted-array 杨辉三角 pascals-triangle 杨辉三角 II pa
大批 两次求和 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 ...