文档章节

解析一道百度面试算法题目

aliasok
 aliasok
发布于 2016/02/02 12:24
字数 414
阅读 88
收藏 0

题目:给定一列有序数组,元素有多个重复值,如[1,1,2,3,3,8,8],求查找元素的最左位置,如存在返回在数组中的下标,不存在返回-1。

  • 思路一
    咋看这是一个二分查找的问题,但是又有所不同,因为二分查找的结果可能查找到重复元素的一个随机的位置,而不是最左位置。
    最简单的想法就是用二分查找,找到元素后在向左遍历,直到找到不相同的元素位置。

代码示例:

// 二分查找最左元素 
function binSearchLeft($arr, $key)
{
    $low = 0;
    $high = count($arr) - 1;
    while ($low + 1 != $high) {
        $mid = intval(($high + $low) / 2);
        if($arr[$mid] == $key){
            //向左遍历找到最左的元素
            while($arr[$mid-1] == $arr[$mid])
            {
                $mid--;
            }
            return $mid;
        } else if($arr[$mid] > $key){
           $high = $mid + 1;
        } else {
           $low = $mid - 1;
        }
    }
    return -1;
}


算法复杂度:O(n/2)

 

  • 思路二
    二分查找的思路就是每次将查找区间缩小一半,直到最后找到结果,那么将这个思路延伸一下解决本题问题:将区间无线聚合缩小,直到最后相邻的两个元素,那么在对这两个元素进行简单判断就可以了。

代码示例:

// 聚合查找区间查找最左元素
function findLeft($arr, $key)
{
    $low = 0;
    $high = count($arr) - 1;
    while ($low + 1 != $high) {
        $mid = intval(($high + $low) / 2);
        if($arr[$mid] >= $key){
           $high = $mid;
        } else {
           $low = $mid;
        }
    }
    if($arr[$high] == $key)
    {
        return $arr[$low] == $arr[$high] ? $low : $high;
    }
    return -1;
}


算法复杂度:O(?) <= O(n/2),算法上更优

如果你有更好的解法,欢迎留言探讨。

© 著作权归作者所有

共有 人打赏支持
aliasok
粉丝 1
博文 9
码字总数 6658
作品 0
朝阳
高级程序员
微软等公司数据结构+算法面试100题

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / / 6 14 / / / / 4 ...

chambai
2012/08/05
0
0
白话经典算法系列之十 一道有趣的GOOGLE面试题

微博http://weibo.com/MoreWindows已开通,欢迎关注。 最近在微博上看到一道有趣的GOOGLE面试题,见下图: 文字版: 一个大小为n的数组,里面的数都属于范围[0, n-1],有不确定的重复元素,找...

长平狐
2012/12/10
91
0
前端笔试、面试

让 BAT 的 Offer 不再难拿 随着各大公司春招的开始,很多小伙伴都行动起来了,我有幸能够加入百度并和大家分享自己的经验心得。由于我面试的都是比较大的公司,所以自然也是做了这方面的准备...

掘金官方
01/11
0
0
小米面经-技术岗(编程小白如何进阶)

先介绍下背景,我本科专业是硬件转软件方面,所以一开始算法基础比较差,没有做过系统设计,为了能得到好的面试机会,我一直都有努力准备,还在网上关注了各种能提高编程能力的攻略,我觉得打...

coderer
2017/05/08
0
0
【白话经典算法系列之十一】一道有趣的GOOGLE面试题 --【解法2】

微博http://weibo.com/MoreWindows已开通,欢迎关注。 本系列文章地址:http://blog.csdn.net/MoreWindows/article/category/859207 上一篇《白话经典算法系列之十一道有趣的GOOGLE面试题》中...

长平狐
2012/12/10
197
0

没有更多内容

加载失败,请刷新页面

加载更多

阿里开源的 java 诊断工具—— Arthas

Arthas 是 阿里巴巴最近开源出来的一个针对 java 的工具,主要是针对 java 的问题进行诊断! 一、概述 这个工具可以协助你做下面这些事情: 这个类是从哪个 jar 包加载而来的? 为什么会报各...

xiaomin0322
19分钟前
1
0
去除shell read 读取的最后一个字符

# 读取管道数据cat | while read line; do echo $line # 此时 line包含 \n or \r\ndone# 去除 read 读取的特殊字符line=${line%?} # 去除最后一个字符...

tigerBin
20分钟前
1
0
Qt之listView设置编辑状态

QListView默认是可以编辑的,可以用setEditTrigers设置QListView的条目是否可以编辑,以及如何进入编辑状态。比如: ui->listView->setEditTriggers(QAbstractItemView::DoubleClicked | QAb...

OceanStar
20分钟前
1
0
Linux批量替换

sed -i "s/http://cache.co188.com///image.co188.com/g" grep http:\/\/image.co188.com -rl . *.html sed -i "s/http://cache.co188.com///cache.co188.com/g" grep http:\/\/cache.co188.......

cpaku
30分钟前
1
0
设置plsql永久注册码

填写注册码: Product Code:4t46t6vydkvsxekkvf3fjnpzy5wbuhphqz serial Number:601769 password:xs374ca...

小橙子的曼曼
35分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部