35. Search Insert Position

题目描述:

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

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 4:

Input: [1,3,5,6], 0
Output: 0

题目翻译

给定一个target,和有序序列,如果target在序列中,则返回其索引,否则给出当插入target且不改变序列性质时插入的位置(索引)。

解题方案

标签: 二分查找

思路: 思路是二分查找,找到就很简单直接返回,没找到,这个时候判断nums[low]和target的关系。

注意一点,比如说现在序列为 0 1 2 3 4 5 6 现在加入target是2,且low为1(nums[low]\==1),则返回索引为low+1 =2 如果target是0,且low为1(nums[low]\==1),则返回索引就是low而不是low-1了。具体原因画一下就清楚了。

这个题的关键还是考察二分查找完成时索引low和索引high的状态。

代码:

class Solution {  
public:  
    int searchInsert(vector<int>& nums, int target) {  
        int len = nums.size() - 1;  
        int low = 0;  
        int high = len - 1;  
        int mid;  
        while (low <= high)//标准二分查找  
        {  
            mid = low + (high - low) / 2;  
            if (nums[mid] == target)  
                return mid;//找到元素  
            else if (nums[mid] > target)  
                high = mid - 1;  
            else  
                low = mid + 1;  
        }  
        //没找到时判断与nums[low]的关系  
        if (target > nums[low])  
            return low + 1;  
        else  
            return low;  
    }  
};

参考资料

results matching ""

    No results matching ""