LeetCode | 35.搜索插入位置

这次来写一下 LeetCode 的第 35 题，搜索插入位置。

题目描述

题目直接从 LeetCode 上截图过来，题目如下：

这个题目是要对给定的值在数组中找到合适的插入位置，而且数组是有序的。

问题分析

这个题目中要求将给定的值在一个有序的数组中找到合适的插入位置，也就说将给定的值插入到数组后，数组仍然保持有序。这个题目可以通过二分法来查找合适的位置，因为数组是有序的，这样的时间复杂度是O(logN)。也可以通过顺序遍历整个数组来进行查找合适的插入位置，但是这样的话时间复杂度会高一些，它的时间复杂度为O(N)。

我以为使用直接遍历整个数组的方式无法通过该题目，但是竟然通过了，那么就直接贴出遍历数组的代码吧。

代码实现

代码实现如下：

int searchInsert(int* nums, int numsSize, int target){
    int i = 0;

    for (; i < numsSize; i ++) {
        if (target <= nums[i]) {
            break;
        }
    }

    return i;
}

提交结果

在写完 searchInsert 函数体后，点击右下角的 “执行代码”，然后观察 “输出” 和 “预期结果” 是否一致，一致的话就点击 “提交” 按钮。点击 “提交” 按钮后，系统会使用更多的测试用例来测试我们写的函数体，如果所有的测试用例都通过了，那么就会给出 “通过” 的字样，如果没有通过，会给出失败的那一组测试用例，我们继续修改代码。我们以上代码 “提交” 以后的截图如下：

可以看到，这样的代码用时果然很多，我一度以为会超时，竟然没有超时，暂时先这样，以后有机会再返回来修改吧。