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.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

代碼

class Solution {
public:
    int searchInsert(vector &nums, int target) {
        if(nums.size() < 1) {
            return 0;
        } else if(nums.size() == 1) {
            if(nums[0] > target) return 0;
            else if(nums[0] == target) return 0;
            else return 1;
        } else {
            int flag = 0;   
            if (nums[0] > target) return 0;
            if(nums[nums.size() - 1] < target) return nums.size();
            for(int i = 0; i <= nums.size() - 1; ++ i) {
                if(nums[i] == target) return i;
                else if (nums[i] < target) flag = i;
                else {
                    if(flag == i - 1) return i;
                }
            }
        }
    }
};

在網上又看到這種了，分享給大家……

class Solution {
public:
    int searchInsert(vector& nums, int target) {
        return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
    }
};