leetcode-35- 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.

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,感谢分享。侵删。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java帮帮-微信公众号-技术文章全总结

第五天 方法【悟空教程】

2067
来自专栏潇涧技术专栏

Python Data Structures - C2 Sort

参考内容: 1.Problem Solving with Python Chapter5: Search and Sorting online_link ...

881
来自专栏用户2442861的专栏

python 中迭代多个序列

http://blog.csdn.net/he_jian1/article/details/40819407

672
来自专栏北京马哥教育

看完这篇文章还不懂Python中的闭包,请拍死小编

1774
来自专栏数据结构与算法

P3370 【模板】字符串哈希

题目描述 如题,给定N个字符串(第i个字符串长度为Mi,字符串内包含数字、大小写字母,大小写敏感),请求出N个字符串中共有多少个不同的字符串。 友情提醒:如果真...

2974
来自专栏程序员互动联盟

【编程基础】聊聊C语言-常用运算符

上一篇我们讲了C语言中的基本运算符,他们就像基石一样奠定了我们进行基本算术运算的基础。我们马上将上一篇留得题的答案公布如下: 5/4=1 5.0/4=1.250...

3967
来自专栏Golang语言社区

第十一节 Go语言数组

干货来了!!!为了让更多的小伙伴喜欢Golang、加入Golang之中来,Golang语言社区发起人彬哥联合业界大牛共同推出了Go语言基础、进阶、提高课程,目前...

1043
来自专栏Python小屋

Pythonic:递归、回溯等5种方法生成不重复数字整数

问题描述:从0到9这10个数字任选3个不重复的数字,能构成哪些三位数? So easy!看到这样的问题,很多人会写出类似(注意,只是类似,我为了使得本文几个函...

4057
来自专栏工科狗和生物喵

【计算机本科补全计划】C++ Primer:指针和const限定符

正文之前 今天下午看了一下午的计算机组成与设计,结果好死不死的看到了设计部分--处理器的设计。天哪,我现在还只是一个准备给人装一台电脑做实验田的家伙,连用都不咋...

2804
来自专栏阿凯的Excel

Python读书笔记(数字型数据)

Python与其它编程语言一样,常见的数字型无法整型(int)和浮点型两种(Float)两种。 整型就是整数,浮点型就是小数。 如果在Python中输入一个数字...

3775

扫码关注云+社区

领取腾讯云代金券