35.搜索插入位置[easy]

LeetCode 算法题停止更新，请移步至 GitHub。

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例

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

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

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

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

解题方法

1.

1. target 在数组中存在的情况，for 循环对比元素相等返回下标即可。

2. target 不存在需要插入数组中的情况，由于数组是有序的，插入到第一个大于 target 的元素中即可。

3. target 不存在并且需要插入到数组尾部的情况，直接返回数组末尾+1的下标（数组原来的长度）即可。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        
        if (n == 0) return 0;
        
        for (int i = 0; i < n; i++) {
            if (nums[i] == target) {
                return i; // 有相等的值
            } else if (nums[i] > target) {
                return i; // 无相等的值并且 i < n
            }
        }
        return n; // target 插入到数组末尾的情况
    }
};

状态	执行用时	内存消耗
通过	16 ms	8.8 MB

时间复杂度：O(n)

空间复杂度：O(1)