Bloomberg电面

lxr 发表于 2016-4-24 08:59
lol 有时应该只是用的电脑没有中文输入法

也有道理！以后要打拼音验证！！

楼主您好~~~请问第一题“在前升后降的array里找某一个数”，这是O(n)呢，还是先binary search 找peak, 然后再peak 两边分别做binary search? 谢谢啊！

一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点击帖子下方的"好苗""分享""收藏"键，酌情给楼主加大米（系统不扣你自己的分）。
积分不够看不了帖子，请参考论坛导航里的"帮助"，"新手提纲"里有攒积分指南

ninacc 发表于 2016-4-25 02:17
楼主您好~~~请问第一题“在前升后降的array里找某一个数”，这是O(n)呢，还是先binary search 找peak, 然后 ...

直接binary search, 根据arr[mid]两边数值情况可以知道是在peak left or peak right?

ninacc 发表于 2016-4-25 02:17
楼主您好~~~请问第一题“在前升后降的array里找某一个数”，这是O(n)呢，还是先binary search 找peak, 然后 ...

O(n)做了一下然后follow up。直接binary search比较两个数组里的mid就可以找出来！类似latched Median of two sorted arrays的做法

jessicachum 发表于 2016-4-25 03:24
O(n)做了一下然后follow up。直接binary search比较两个数组里的mid就可以找出来！类似latched Median of ...

到第一个数组还是两个数组?
你的中文描述好像印度人 :)

freemail165 发表于 2016-4-25 03:30
到第一个数组还是两个数组?
你的中文描述好像印度人 :)

一个数组呀。。但是我觉得思想有点类似吧，把两边分别看成一组升序的数。就都是两边各找一个数，然后比较一下大小，决定不要哪边的数！我是那么做的，测了几组数结果都是对的
我不是印度人，但是我语文不好谢谢

jessicachum 发表于 2016-4-24 14:36
一个数组呀。。但是我觉得思想有点类似吧，把两边分别看成一组升序的数。就都是两边各找一个数，然后比较 ...

谢谢啊！在请问楼主, 那你说的是rotated array吧？ 比如 3 4 5 1 2 这样的。但是帖子说的数组是前升后降，就比如[3,5,7,8,6,4,2]。

ninacc 发表于 2016-4-25 08:06
谢谢啊！在请问楼主, 那你说的是rotated array吧？ 比如 3 4 5 1 2 这样的。但是帖子说的数组是前升后降 ...

是[3,5,7,8,6,4,2] 这样的，我是说一个index从0开始，另一个index从数组的最后面开始，这个意思。

jessicachum 发表于 2016-4-25 08:08
是[3,5,7,8,6,4,2] 这样的，我是说一个index从0开始，另一个index从数组的最后面开始，这个意思。

如果是[3,5,7,8,6,4,2]这种形式的，用binary search, 不好判定不要哪边的数吧。比如找4，第一次mid的位置上是8，那前半部分的范围是（3，8），后半部分是（2，8），两个范围都包含了4，那是要继续对两边都进行binary search? 略迷茫