leetcode-004-搜索插入位置
刷题之旅从数组类型的题目开始。第四道题目是移除元素,对应leetcode的题号为35。
题目描述
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
1 | 输入: [1,3,5,6], 5 |
示例 2:
1 | 输入: [1,3,5,6], 2 |
示例 3:
1 | 输入: [1,3,5,6], 7 |
示例 4:
1 | 输入: [1,3,5,6], 0 |
解题思路
其实最简单的方式是直接遍历有序数组,因为这个题目并没有要求要把target插入到数组指定位置,只需要返回需要插入的索引即可,那我们直接一个一个往后寻找即可。
1 | class Solution { |
不过当数据量很大的时候,比如这个有序数组有几十万数据,那么从头遍历的效率会比较低,那么就需要有一定的跳跃来减少不必要的查询,那么由于是有序数组,第一个想到的必然就是二分查找法,直接能把搜索的返回缩小为原来的一半,有效提高效率。
提交代码
1 | class Solution { |