文档章节

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

aliasok
 aliasok
发布于 2016/02/02 12:24
字数 414
阅读 92
收藏 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
99
0
微软等公司数据结构+算法面试100题

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

chambai
2012/08/05
0
0
百度第三面被拒,总结了下希望能对大家有帮助

在线投简历: 在百度网站上直接投的,效率很快,当天就通过筛选了,第二天中午就通知让进行在线笔试。 在线笔试: 根据协议,就不公开了,还是要讲诚信的,题目都是网上公布的,都能搜到。 ...

王海峰
2011/04/14
19K
101
看「百度都能一分钟搜索的面试题」帖子有感

楼主想必是对该面试官提问百度都能搜出答案的嗤之以鼻。 虽然我不太清楚该面试官的题目有多简单,但是我有必要为这个可怜的面试官辩解说两句。 我也算是面试过很多人了,答题也是自己编写的,...

会员
2015/08/11
4.2K
25
[转载]9个offer,12家公司,35场面试,从微软到谷歌,应届计算机毕业生的2012求职之路

1,简介 毕业答辩搞定,总算可以闲一段时间,把这段求职经历写出来,也作为之前三个半月的求职的回顾。 首先说说我拿到的offer情况: 微软,3面->终面,搞定 百度,3面->终面,口头offer 搜狗...

蟋蟀哥哥
2013/01/10
8.4K
50

没有更多内容

加载失败,请刷新页面

加载更多

Linux 权限

权限 0 000 --- 无权限 1 001 --x 执行权限 2 010 -w- 写权限 3 011 -wx 写和执行 4 100 r-- 读权限 5 101 r-x 读和执行 6 110 rw- 读和写 7 111 rwx 读写执行 755 : rwxr-xr-x 660 : rw-r...

忙碌的小蜜蜂
16分钟前
0
0
21分钟教会你分析MaxCompute账单

21分钟教会你分析MaxCompute账单 背景 阿里云大计算服务MaxCompute是一款商业化的大数据分析平台,其计算资源有预付费和后付费两种计费方式。并且产品每天按照project为维度进行计量计费(账...

阿里云云栖社区
19分钟前
0
0
Docker使用 linuxserver/letsencrypt 生成SSL证书最全解析及实践

本文使用 HTTP 和 DNS 两种校验方式对 Docker 下 linuxserver/letsencrypt 项目进行了实践。生成SpringBoot可用证书,使用 Nginx 的 htpasswd 来对网站进行密码保护,并测试使用 fail2ban 防...

java菜分享
20分钟前
0
0
代码吃鸡:Python-Robocode

最近看到一个很有“未来感”的新闻: 一辆特斯拉在拉斯维加斯出了车祸,撞“死”了一个……emmmm……机器人。不知道是意外还是炒作,又或者是这位机器人故意碰瓷,反正人们也无法从受害者口中...

crossin
24分钟前
0
0
什么是公网IP、内网IP和NAT转换?

搞网络通信应用开发的程序员,可能会经常听到外网IP(即互联网IP地址)和内网IP(即局域网IP地址),但他们的区别是什么? 1、引言 搞网络通信应用开发的程序员,可能会经常听到外网IP(即互联网I...

Linux就该这么学
34分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部