文档章节

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

aliasok
 aliasok
发布于 2016/02/02 12:24
字数 414
阅读 85
收藏 0
点赞 1
评论 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
让我印象深刻的 JavaScript 面试题

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

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

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

天天顺利
05/18
0
0
百度2010暑期实习笔试面试全面备战

百度2010暑期实习笔试面试全面备战 百度2010暑期实习网申将于2010年5月29日截止。 笔试阶段 5月30日前,对于通过了简历筛选的申请人百度将会通过系统发送笔试通知。注册时请务必填写正确有效...

长平狐
2013/01/06
105
0
2014年计算机求职总结--准备篇

版权所有,转载请注明出处,谢谢! http://blog.csdn.net/walkinginthewind/article/details/13000431 找工作是一个长期准备的过程,突击是没什么效果的。准备时间越长,准备就越充分,就越容...

u011729265
2013/10/27
0
0
2014-10-18 多玩初面

今天又从东莞来到广州,真心累,首先我是校招,星期五那天笔试过了。 下午一点的时候来到广州华工大学中心酒店,这次也是首次面试互联网公司吧,上次去腾讯未果。 坐下来,面试官就问,你搞过...

moz1q1
2014/10/18
0
2

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Spark Streaming + Kafka Integration Guide

The Spark Streaming integration for Kafka 0.10 is similar in design to the 0.8 Direct Stream approach. It provides simple parallelism, 1:1 correspondence between Kafka partition......

刺猬一号
11分钟前
0
0
数据结构与算法2

一个数组的例子,实现查找,显示和删除的功能。 在这个数组中存储的数据类型是long型,使用long型为的是表明这是数据,而int型被用来表示下标。通常数据结构存储的数据项包含有好几个字段,所...

沉迷于编程的小菜菜
22分钟前
0
0
Python3 基于 requests 批量下载图片

Python3 基于 requests 批量下载图片 import requestsheaders = {'Accept': 'text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,image/apng,*/*;q=0.8','Accept-Encod......

leeyi
22分钟前
0
0
java获取当前时间所在一周的周一和周日日期

/** * 当前时间所在一周的周一和周日时间 * @param time 当前时间 * @return */ public static Map getWeekDate(String time) { Map map = new HashedMap(); SimpleDateFormat sdf = new Si......

小弱鸡
54分钟前
0
0
Redis数据的导出和导入(dump和load方式)

网上有些文章已经不再适用,本人也是踩了些坑,在此记录下。 迁移redis数据一般有如下3种方式: 第三方工具redis-dump,redis-load aof机制,需要开启aof功能 rdb存储机制 这里介绍第一种方式...

iplusx
59分钟前
2
0
ElasticSearch 高亮显示大文档搜索结果

2016年12月,我们开始研究Ambar——一个文档搜索系统。Ambar使用ElasticSearch作为核心搜索引擎。 在Ambar开发的过程中,我们处理了很多与ES相关的问题,我们想分享我们得到的宝贵经验。让我...

九州暮云
今天
1
0
Python 使用 pywifi 模块 破解wifi密码

git https://github.com/awkman/pywifi 常见常量 from pywifi import const# Define interface status.IFACE_DISCONNECTED = 0IFACE_SCANNING = 1IFACE_INACTIVE = 2IFACE_CONNEC......

阿豪boy
今天
2
0
phpstorm使用Iedis

phpstorm的redis插件Iedis是真好用 看了网上挺多的文章,但是由于我系统还是ubuntu,就有点尴尬了,现在破解之后,留个笔记,即使自己之后有需要也可以很快翻阅 先下载资源 资源下载 zip压缩...

贤郎--均灵
今天
0
0
第三章 spring-bean之FactoryBeanRegistrySupport(4)

前言 从FactoryBeanRegistrySupport类的名字可以看出FactoryBeanRegistrySupport负责FactoryBean的注册与支持。如果想知道FactoryBean相关的资料,请阅读spring-bean中关于FactoryBean的解读...

鸟菜啊
今天
0
0
CentOS “Destination Host Unreachable”问题解决办法

挑战极速安装CentOS时遇到局域网主机不能通信的情况: [root@zjd network-scripts]# ping 8.8.8.8PING 8.8.8.8 (8.8.8.8) 56(84) bytes of data.64 bytes from 8.8.8.8: icmp_seq=1 ttl=......

wffger
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部