TikTok电面跪经

上个月面的字节ads组，

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

断但是不知道怎么应用到descending的情况。。不知道各位有没有什么好的思路呢

最坏情况应该是O(n)，如果一个数组所有元素都一样或者只有一个是target，那么肯定无法二分。

平均Log复杂度的话就是比较首中尾三个值 (L, M, R)
if L > R -> M在两者中间则单调下降无shift，否则是shift升序
if L < R -> M在两者中间则单调上升无shift，否则是shift降序
if L = R -> 则首尾同时向里平移一位，这里就是为什么最坏会退化成O(n)

420402033 发表于 2022-5-15 15:16
去重不是直接O(n)了吗。。
不过第二个点好，二分搜索的时候可以对descending的取负，这样二分完全不用改

我说的先去重是首尾去重，用来判断ascending和descending的。虽然这个有可能会O(n)，但是你在二分过程中去重最差也得O(n)。不过我也不确定是不是可以这样做。还有更好的方法可以判断递增减吗？

可以透露一下什么题吗？没米看不到😀

joey.zh.cn 发表于 2022-5-6 09:20
可以透露一下什么题吗？没米看不到😀

咦奇怪我没有设大米限制啊。

--> 题目是利抠靶依的变种，增加了两个限制要求，第一个是必须要在O(logN)完成，第二个是不知道原来array是ascending还是descending

应该就先比较两个数，确定是升序还是降序。然后在二分搜

jianpanxia 发表于 2022-5-10 22:17
应该就先比较两个数，确定是升序还是降序。然后在二分搜

具体怎么做比较呢？因为你可能正好选到断点，导致判断相反

420402033 发表于 2022-5-11 16:42
具体怎么做比较呢？因为你可能正好选到断点，导致判断相反

比较头和尾？

微信用户_7bf6897 发表于 2022-5-11 02:13
比较头和尾？

有道理，想了一下可以头尾各比三个数，
如果两组一致就可以统一判断升序还是降序，如果不一致那一定一边有断点，就可以通过没有断点的那一侧判断。
如果size<5直接遍历，因为可能会出现两边都有断点ie. [3,4,1,2]

420402033 发表于 2022-5-11 02:36
有道理，想了一下可以头尾各比三个数，
如果两组一致就可以统一判断升序还是降序，如果不一致那一定一边 ...

如果数组中的数字可以有重复，那这个方法看起来不太行。应该比较首、尾、中三个数。

英伦十六世纪 发表于 2022-5-11 23:11
如果数组中的数字可以有重复，那这个方法看起来不太行。应该比较首、尾、中三个数。

有道理！但是如果只对比首尾中，那万一shift之后首尾一样好像也没法判断？比如2223122

面试官比较坑，这种好歹让你先写一下吧