0%

[0035] 搜索插入位置

发表于 更新于 分类于 ， 本文字数： 1.4k 阅读时长 ≈ 1 分钟
...

[0035] 搜索插入位置

题目描述

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

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

示例 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

Related Topics
  • 数组
  • 二分查找

    • 题目解析

    • 本题是一道查找题

    不确定性

    方法一：顺序查找法

    分析

    • 在数组中顺序比较组内元素和目标值的大小，找到需要插入的位置

    思路

    • 利用变量i遍历数组，若出现组内元素大于等于目标值时，则该位置就是需要插入的位置
    • 若遍历完整个数组，则说明目标值大于数组中最大元素，则插入位置在数组末尾

    注意

    • 比较时注意排序数组中已有目标值的情况

    知识点

    • vector的遍历

    复杂度

    • 时间复杂度 O(n)
    • 空间复杂度 O(1)

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    int searchInsert(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i++){
            if (nums[i]>=target){
                return i;
            }
        }
        return nums.size();
    }

    方法二：二分查找法

    分析

    • 因为是数组递增，所以可以使用靠中间的值与目标值进行比较
    • 若目标值大了，则可以查找后半段数组；反之，则查找前半段数组

    思路

    • 利用low和high分别指向数组的开头和结尾，mid则为中间位置
    • 若target>nums[mid]，则令low = mid + 1
    • 若target<nums[mid]，则令high = mid - 1
    • 若target=nums[mid]，则返回位置mid
    • 重复执行上述步骤，直到low>high时，在nums没有找到时

    注意

    • 在编写代码时，low<=high中的“=”不要忘记

    知识点

    • 二分查找

    复杂度

    • 时间复杂度 O(log(n))
    • 空间复杂度 O(1)

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    int searchInsert(vector<int>& nums, int target) {
    	int low = 0, high = nums.size() - 1;
    	while (low <= high){
    		int mid = (low + high) / 2;
    		if (nums[mid] > target){
    			high = mid - 1;
    		}
    		else if (nums[mid] < target){
    			low = mid + 1;
    		}
    		else{
    			return mid;
    		}
    	}
    	return low;
    }

    相关题目

    相关文章