• 欢迎访问梯云博客,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站点击访问
  • 站点的评论回复邮件可能会被邮箱放入垃圾邮件中,请注意哦~
  • 梯云博客近期增设了“电影资源”板块,在视频区域下边哦~
  • 梯云音乐上线,提供一站式的音乐下载平台,点击前往梯云音乐
  • 如果百度网盘下载速度过慢,可使用该工具~Proxyee-down 百度网盘不限速
  • 本站所有发布的信息以及产品,仅供学习研究使用;除有软件所有者授权外不得非法用于商业或其他用途。
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏梯云吧!

[LeetCode] 35题 搜索插入位置(Search Insert Position)

数据结构/算法 做棵大树 1个月前 (05-18) 76次浏览 1个评论
文章目录[隐藏]

搜索插入位置(Search Insert Position)

题目要求

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

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


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

解法

对于这个问题,我们可以采取两种方式进行解决:

  1. 遍历整个数组 ( 最优时间复杂度 O(1),最坏 O(n) )
int len = nums.length;
if (len == 0) return 0; // if the nums is empty, return 0
for(int i = 0; i < len; i++) {
    if(target <= nums[i]) {  //  when target <= nums[i] , return
        return  i;
    }
}
return len;
  1. 二分法进行查找 ( 2 的 logn 次方等于 n,最坏时间复杂度为 O(logn),最优 O(1) )
int head = 0;
int tail = nums.length;
int mid = 0;
if( nums.length == 0 || target <= nums[head]) return 0;
while(head < tail) {
    mid = ((tail - head) >> 1) + head;
    if(target > nums[mid]) {
        head = mid + 1;
    }else{
        tail = mid;
    }
}
return tail;

TeenShare 梯云分享 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明[LeetCode] 35 题 搜索插入位置(Search Insert Position)
喜欢 (2)
[欢迎投币]
分享 (0)
关于作者:
一个整天无所事事的,有时候忽然热血的孩子
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
(1)个小伙伴在吐槽
  1. 文章不错支持一下,非常喜欢
    今日头条新闻2019-05-23 00:08 回复 Windows 7 | Chrome 63.0.3239.132