leetcode35题:搜索插入位置

发布时间:2024年01月23日



一、题目描述?

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

示例 1:

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

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

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

二、不同时间复杂度的代码实现以及讲解

1.时间复杂度:O(n)

代码如下:

 public int searchInsert(int[] nums, int target) {
    int n = nums.length;
    int index = 0;
    if (target > nums[n - 1]) {
        return n;
    }
    for (int i = 0; i <= n - 1; i++) {
        if (nums[i] == target) {
            index = i;
            break;
        }
        if (target > nums[i] && target < nums[i + 1]) {
            index = i + 1;
            break;
        }
    }
    return index;
}

代码讲解:

  1. 定义变量 n 并赋值为数组 nums 的长度,表示数组的大小。

  2. 定义变量 index 并初始化为 0,用于记录目标值的索引位置或插入位置。

  3. 首先检查目标值是否大于数组中最后一个元素 nums[n-1],如果是,则说明目标值应该插入到数组末尾,直接返回数组的长度 n。

  4. 使用 for 循环遍历数组,从前往后进行比较:

  5. 如果当前元素 nums[i] 等于目标值,将 index 设置为当前索引 i。

  6. 如果目标值大于当前元素 nums[i],且小于下一个元素 nums[i+1],则目标值应该插入到当前元素之后,将 index

  7. 设置为当前索引 i+1。 注意循环条件为 i <= n - 1,以确保在遍历到最后一个元素时仍然可以执行判断。

  8. 循环结束后,将 index 返回作为结果。

2.时间复杂度:O(log n)

代码如下:

 public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (target <= nums[mid]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

代码讲解:

  1. 定义变量 n 并赋值为数组 nums 的长度,表示数组的大小。
  2. 定义变量 left 并初始化为 0,表示当前搜索范围的左边界。
  3. 定义变量 right 并初始化为 n - 1,表示当前搜索范围的右边界。
  4. 定义变量 ans 并初始化为 n,用于记录目标值的索引位置或插入位置。
  5. 进入循环,当 left 小于等于 right 时,执行以下操作:
  6. 计算中间元素的索引 mid,通过将 (right - left) >> 1(右移一位相当于除以2)加上 left 得到。
  7. 如果目标值小于等于中间元素 nums[mid],则更新 ans 为 mid,并将搜索范围缩小到左半部分,即将 right 更新为 mid - 1。
  8. 否则,目标值大于中间元素,将搜索范围缩小到右半部分,即将 left 更新为 mid + 1。
  9. 循环结束后,返回 ans。
文章来源:https://blog.csdn.net/weixin_67589420/article/details/135777834
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。