查看: 1485| 回复: 2
跳转到指定楼层
上一主题 下一主题
收起左侧

[CareerCup] CC150 Chapter 10 Sorting and Searching 10.3 题干疑问

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
CC150 第五版
10.3 Given a sorted array of n integers that has been rotated an unknown number of times, write code to find an element in the array. You may assume that the array was originally sorted in increasing order.  

这个题都是说和leetcode的search in rotated sorted array 一样的,一般都是讲rotated了一次
像这样{15,16,19,20,25,1,3,4,5,7,10,14}。
二分法每次就可以用中点和两边的值来确定哪边是递增哪边是rotated了从而缩小范围。

但这题题干说是rotated an unknown number of times,这是什么意思?rotated 很多次的意思?
不就变成类似这样
{1,3,4,5,15,16,19,20,25,7,10,14}
挺让人confused,不仅没规律可循了,而且极端情况不就无序了,这题不就有问题了嘛?

我可能逗比了,大家来解下惑,谢谢了

上一篇:分享把leetcode上面的文章转成的书
下一篇:看到一道随机数生成的算法题
全局:
不管rotate多少次,和rotate一次是差不多的,楼主可以试一下,比如
【1,2,3,4,5,6,7】-----》【5,6,7,1,2,3,4】再从2和3之间rotate一次----------》【3,4,5,6,1,2】
回复

使用道具 举报

🔗
stellari 2015-2-28 14:14:41 | 只看该作者
全局:
Leetcode上的一次rotation指的是“左移n位”,或者“右移n位”。这个题的rotation则的指是“左移一位”或者“右移一位”,所以它需要多说一句“unknown number of times”来补上“n位”这个意思。本质和leetcode上的表述是一样的。
回复

使用道具 举报

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

本版积分规则

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