迪子秋招
当大家看到这个消息的时候，迪子秋招已经只要双 2 以上了。
曾经你对迪子爱搭不理，现在迪子让你高攀不起。
谁能想到，大概是三四年前迪子还是大家的备选，经常被同学们戏称 迪子招聘，点击就送 offer。去年则摇身一变，网络口号变成 迪爹，感谢收留，现在直接成了 高攀不上，迪迦！🤣🤣🤣
这一切的背后，还是供大大大大大于求，传言这一次迪子秋招，系统开放不足 24 小时收到了近 20W 份简历，这个数量级的简历，HR 明年都看不完。因此，迪子采取了最简单直接的做法：在招聘系统设定学历要求，快速筛选候选人。
对此，你怎么看？你所在的行业/公司，是否也出现了类似的学历膨胀？
...
回归主题。
来一道和「秋招」相关的算法题。
题目描述
平台：LeetCode
题号：154
已知一个长度为 n 的数组，预先按照升序排列，经由 到 次旋转后，得到输入数组。
例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
若旋转 次，则可以得到 [4,5,6,7,0,1,4]若旋转 次，则可以得到 [0,1,4,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个可能存在「重复」元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。
请你找出并返回数组中的「最小元素」。
示例 1：
输入：nums = [1,3,5]
输出：1
示例 2：
输入：nums = [2,2,2,0,1]
输出：0
提示：
nums原来是一个升序排序的数组，并进行了 至 次旋转
进阶：
这道题是「寻找旋转排序数组中的最小值」的延伸题目。 允许重复会影响算法的时间复杂度吗？会如何影响，为什么？
二分
根据题意，我们知道，所谓的旋转其实就是「将某个下标前面的所有数整体移到后面，使得数组从整体有序变为分段有序」。
但和 153. 寻找旋转排序数组中的最小值 不同的是，本题元素并不唯一。
这意味着我们无法直接根据与* *的大小关系，将数组划分为两段，即无法通过「二分」来找到旋转点。
因为「二分」的本质是二段性，并非单调性。只要一段满足某个性质，另外一段不满足某个性质，就可以用「二分」。
如果你有看过我 严格 O(logN)，一起看清二分的本质 这篇题解，你应该很容易就理解上句话的意思。如果没有也没关系，我们可以先解决本题，在理解后你再去做 153. 寻找旋转排序数组中的最小值，我认为这两题都是一样的，不存在先后关系。
举个🌰，我们使用数据 [0,1,2,2,2,3,4,5] 来理解为什么不同的旋转点会导致「二段性丢失」：
Java 代码：
class Solution {
public int findMin(int[] nums) {
int n = nums.length;
int l = 0, r = n - 1;
while (l < r && nums[0] == nums[r]) r--;
while (l < r) {
int mid = l + r + 1 >> 1;
if (nums[mid] >= nums[0]) l = mid;
else r = mid - 1;
}
return r + 1 < n ? nums[r + 1] : nums[0];
}
}
C++ 代码：
class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size();
int l = 0, r = n - 1;
while (l < r && nums[0] == nums[r]) r--;
while (l < r) {
int mid = l + r + 1 >> 1;
if (nums[mid] >= nums[0]) l = mid;
else r = mid - 1;
}
return r + 1 < n ? nums[r + 1] : nums[0];
}
};
Python 代码：
class Solution:
def findMin(self, nums: List[int]) -> int:
n = len(nums)
l, r = 0, n - 1
while l < r and nums[0] == nums[r]:
r -= 1
while l < r:
mid = l + r + 1 >> 1
if nums[mid] >= nums[0]:
l = mid
else:
r = mid - 1
return nums[r + 1] if r + 1 < n else nums[0]
TypeScript 代码：
function findMin(nums: number[]): number {
const n = nums.length
let l = 0, r = n - 1
while (l < r && nums[0] == nums[r]) r--
while (l < r) {
const mid = l + r + 1 >> 1
if (nums[mid] >= nums[0]) l = mid
else r = mid - 1
}
return r + 1 < n ? nums[r + 1] : nums[0]
};
时间复杂度：恢复二段性处理中，最坏的情况下（考虑整个数组都是同一个数）复杂度是 ，而之后的找旋转点是「二分」，复杂度为 。整体复杂度为 空间复杂度：
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
