leetcode-35- Search Insert Position

chenjx85

发布于 2019-03-14 10:21:12

3300

发布于 2019-03-14 10:21:12

题目描述：

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018-04-03 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度