📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: mycoy
跳转到指定楼层
上一主题 下一主题
收起左侧

Yahoo 电面; LC 33. Search in Rotated Sorted Array, follow-up Questions

全局:
mycoy 发表于 2017-1-15 07:51
这个还不知道啊;
随便找3个连续的数,应该确定不了吧。
一个长数组可以有很多种rotation的。。。

应该只有一个pivot吧,不然这怎么搞呀...直接O(n)会不会被面试官骂死...
回复

使用道具 举报

🔗
appleLeaf 2017-1-16 12:43:34 | 只看该作者
全局:
mycoy 发表于 2017-1-15 07:49
我觉得, 要改边界值,  可能要改比较符号。
比如ascending order, 在循环中会有, if( nums[mid]

判度了之后reverse一下?
回复

使用道具 举报

🔗
appleLeaf 2017-1-16 12:58:33 | 只看该作者
全局:
求是ascending还是descending可不可以用o(n)时间和o(n)时间和o(n)空间求每个数和前一个的差,根据>0和<0的个数来判断?
回复

使用道具 举报

全局:
appleLeaf 发表于 2017-1-16 12:58
求是ascending还是descending可不可以用o(n)时间和o(n)时间和o(n)空间求每个数和前一个的差,根据>0和

如果都O(n)了,那直接就能求到target,还需要判断什么...
回复

使用道具 举报

🔗
appleLeaf 2017-1-17 02:22:40 | 只看该作者
全局:
类与对象tju 发表于 2017-1-16 14:44
如果都O(n)了,那直接就能求到target,还需要判断什么...

哈哈,囧。。。
多谢楼主点拨
回复

使用道具 举报

🔗
 楼主| mycoy 2017-1-18 05:40:39 | 只看该作者
全局:
Update:  刚收到 rejection 邮件
回复

使用道具 举报

🔗
laiguojiuhao 2017-1-18 06:07:11 | 只看该作者
全局:
如果元素没有重复的话,感觉可以比较第一个元素和最后一个元素,如果第一个比最后一个大,ascending,否则descending。rotate的次数没关系,不管怎么rotate都只有一个pivot
回复

使用道具 举报

🔗
laiguojiuhao 2017-1-18 06:17:16 | 只看该作者
全局:
laiguojiuhao 发表于 2017-1-18 06:07
如果元素没有重复的话,感觉可以比较第一个元素和最后一个元素,如果第一个比最后一个大,ascending,否则d ...
  1. class Solution(object):
  2.     def search(self, nums, target):
  3.         """
  4.         :type nums: List[int]
  5.         :type target: int
  6.         :rtype: int
  7.         """
  8.         if not nums:
  9.             return -1
  10.    
  11.         def check(a, b, ascending):
  12.             return a > b if ascending else a < b
  13.    
  14.         def inBetween(end1, end2, mid):
  15.             return min(end1, end2) <= mid <= max(end1, end2)
  16.    
  17.         beg, end = 0, len(nums)-1
  18.         ascending = nums[beg] > nums[end]
  19.    
  20.         while beg <= end:
  21.             mid = (beg + end) / 2
  22.             if nums[mid] == target:
  23.                 return mid
  24.             if check(nums[mid], nums[end], ascending):
  25.                 if inBetween(nums[beg], nums[mid], target):
  26.                     end = mid-1
  27.                 else:
  28.                     beg = mid+1
  29.             else:
  30.                 if inBetween(nums[mid], nums[end], target):
  31.                     beg = mid+1
  32.                 else:
  33.                     end = mid-1
  34.         return -1
复制代码
写了一下,能过leetcode的ascending的,descending没有测试
回复

使用道具 举报

🔗
 楼主| mycoy 2017-1-19 05:38:13 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表