文档章节

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

aliasok
 aliasok
发布于 2016/02/02 12:24
字数 414
阅读 91
收藏 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
朝阳
高级程序员
私信 提问
白话经典算法系列之十 一道有趣的GOOGLE面试题

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

长平狐
2012/12/10
91
0
微软等公司数据结构+算法面试100题

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

chambai
2012/08/05
0
0
前端笔试、面试

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

掘金官方
01/11
0
0
让我印象深刻的 JavaScript 面试题

1.前言 对于一个web前端来说,面试的时候,难免会遇到javascript的面试题。就我自己而言。有几道面试题,有些是我面试遇到的,有些是在网上看到的,但是都印象深刻。今天就来简单分析一下我遇...

守候i
2017/11/22
0
0
Top K算法详细解析---百度面试

者:码农 问题描述: 这是在网上找到的一道百度的面试题: 搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。假设目前有一千万个记录,这些查...

天天顺利
05/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

DataFrames中的reindex用法

from pandas import DataFrame frame = DataFrame(np.arange(9).reshape((3,3)),index=['a','c','d'],columns=['Ohio','Texas','California'] states = ['Texas','Utah','California'] frame......

卖小孩的小火柴
27分钟前
2
0
拜托!面试请不要再问我Spring Cloud底层原理

毫无疑问,Spring Cloud是目前微服务架构领域的翘楚,无数的书籍博客都在讲解这个技术。不过大多数讲解还停留在对Spring Cloud功能使用的层面,其底层的很多原理,很多人可能并不知晓。因此本...

James-
28分钟前
2
0
Shiro框架

提供了认证,授权,加密,会话管理等功能 在spring配置文件中配置shiro,需要配置的有shiro的过滤器工厂,在里面我们可以配置什么页面需要认证,什么认证不需要认证,认证成功后跳转的路径,认证失败...

tinder_boy
30分钟前
1
0
有关定时任务的表达式--cron 详细解

Cron表达式是一个字符串,字符串以5或6个空格隔开,分为6或7个域,每一个域代表一个含义,Cron有如下两种语法格式: Seconds Minutes Hours DayofMonth Month DayofWeek Year或 Seconds Minu...

kuchawyz
32分钟前
3
0
下一代大数据处理引擎,阿里云实时计算独享模式重磅发布

11月14日,阿里云重磅发布了实时计算独享模式,即用户独享一部分物理资源,这部分资源在网络/磁盘/CPU/内存等资源上跟其他用户完全独立,是实时计算在原有共享模式基础上的重大升级。 (观看...

阿里云云栖社区
33分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部