Leetcode035

LeetCode035：搜索插入位置         给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。 如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 你可以假设数组中无重复元素。 ```cpp 示例 1:

输入: [1,3,5,6], 5
输出: 2
示例 2:

输入: [1,3,5,6], 2
输出: 1
示例 3:

输入: [1,3,5,6], 7
输出: 4
示例 4:

输入: [1,3,5,6], 0
输出: 0

#### 解法一：基于if和for循环的判断 (执行时间4ms, 内存消耗6.5MB)

&#160; &#160; &#160; &#160;<font color="black" size="4">首先定义一个标记new_idx，然后使用基于for范围的遍历数组，
如果数组中的元素n不等于val, 则将n赋值给下标new_idx对应的元素</font>

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

解法二：判断数组中的每一个元素和target的大小 (执行时间4ms, 内存消耗6.7MB)

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

解法三：改写Solution2的for循环，采用auto基于范围的for循环 (执行时间4ms, 内存消耗6.6MB)

class Solution3 {
public:
    int searchInsert(vector<int>& nums, int target) {
        if (nums.empty())
            return 0;
        int i = 0;
        for (auto n : nums)
        {
            if (n >= target)
                return i;
            ++i;
        }
        return i;
    }
};

main()函数

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;


int main()
{
    vector<int> nums;
    cout << "请输入数组的大小Size: " << endl;
    int Size;
    cin >> Size;
    int Currval;
    cout << "请输入数组中的元素: " << endl;
    for (int i = 0; i < Size ; i++)
    {
        cin >> Currval;
        nums.push_back(Currval);
    }
    int target;
    cout << "请输入目标值target: " << endl;
    cin >> target;
    Solution answer;
    cout << "返回的目标索引值为： " << answer.searchInsert(nums,target) << endl;

    system("pause");
    return 0;
}