专栏首页chenjx85的技术专栏leetcode-35- Search Insert Position

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 之 Array 数组

    Java反射技术除了可以在运行时动态地决定要创建什么类型的对象,访问哪些成员变量,方法,还可以动态地创建各种不同类型,不同维度...

    阳光岛主
  • 18.6.12日报

    1,http://vip.58ganji.com/house/publish/ershou/?chooseWeb%5B%5D=2

    龙泉寺扫地僧
  • Android 内存分析工具

    Dalvik 虚拟机支持垃圾收集,但是这不意味着你可以不用关心内存管理。你应该格外注意移动设备的内存使用,手机和平板的内存空间是受到限制的。

    阳光岛主
  • 18.6.6日报,layer太多造成卡慢

    1,跟进http://www.zhangxinxu.com/study/201005/css3-solar-system.html卡慢问题。

    龙泉寺扫地僧
  • 18.6.10日报

    1,把electron的消息、线程模式全改成自己实现,不依赖windows。然后搞定了之前的多年老bug。以前经常死锁,卡死。

    龙泉寺扫地僧
  • Android: couldn't save which view has focus because the focused view ### has no id

    Android: couldn't save which view has focus because the focused view ### has no ...

    阳光岛主
  • 18.6.16日报

    2,修复vscode不能加载新窗口的问题。主要是 script环境创建的太早,是在收到某个ipc消息就创建了。而

    龙泉寺扫地僧
  • JVM学习笔记——垃圾收集器与内存分配策略(1)

    上一篇文章介绍了java运行时内存的各个区域,其中虚拟机栈,程序计数器,本地方法栈三个区域随线程而生,随线程而灭。栈中的栈帧随着方法的进入和退出有条不紊的执行着...

    用户1665735
  • Java 之 String 类型

    因为对象的默认值是null,所以String的默认值也是null;但它又是一种特殊的对象,有其它对象没有的一些特性。

    阳光岛主
  • 18.6.13日报,提示CoInitialize未调用的解决方法

    1,完善electron的拖拽。里面细节较多,和wke模式不同的是需要处理多线程逻辑。

    龙泉寺扫地僧

扫码关注云+社区

领取腾讯云代金券