leetcode-35- Search Insert Position
2018-06-17 20:51:33来源:未知 阅读 ()
题目描述:
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.
Example 1:
Input: [1,3,5,6], 5
Output: 2
Example 2:
Input: [1,3,5,6], 2
Output: 1
Example 3:
Input: [1,3,5,6], 7
Output: 4
Example 1:
Input: [1,3,5,6], 0 Output: 0
要完成的函数:
int searchInsert(vector<int>& nums, int target)
代码:
int searchInsert(vector<int>& nums, int target)
{
if(nums.empty())
return 0;//判断是否为空
else
{
for(int i=0;i<nums.size();i++)
{
if(target==nums[i])
return i;//如果直接能找到就返回
else if(target<nums[i])
return i;//如果不能找到但是找到一个比它大的数,再加上这是一个升序排列的vector,所以这里可以这样处理,会快上很多
}
return nums.size();//如果跑完一遍都没找到等于target的数,也没找到比它大的,那么它只能在最后一位
}
}
说明:
1、这道题目如果按照常规思路,先for循环跑一遍确认target在不在vector里面,如果在就返回index(位置),如果不在,再跑一遍for循环找到第一个比target大的数值,然后输出index。这样会慢上很多。我们不如直接在一个for循环里面搞定。
2、其实这是一道二分查找的题目,二分查找的算法去做会比我的从头到尾遍历一遍的暴力做法更省时间。但可能是因为测试集数据量太小的原因,我找了一个discussion里面的二分查找,跑出来反而比暴力解法慢了。如下:
int searchInsert(vector<int>& nums, int target) {
int low = 0, high = nums.size()-1;
while (low <= high) {
int mid = low + (high-low)/2;
if (nums[mid] < target)
low = mid+1;
else
high = mid-1;
}
return low;
}
这份代码属于leetcode上的用户a0806449540,感谢分享。侵删。
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- InsertionSort(插入排序)原理及C++代码实现 2020-01-14
- C++ map insert 另一个map的子集 2019-10-16
- 一个C++的ElasticSearch Client 2019-08-16
- 【智能算法】变邻域搜索算法(Variable Neighborhood Search, 2018-07-03
- SPOJ7258 SUBLEX - Lexicographical Substring Search(后缀 2018-06-29
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash