题目分析
题目的数据量是1e7,暴力法可以直接通过,小伙伴们能否想到更优的方法?
二分查找
题目的意图是让我们使用二分查找来解决这个题目,题意中明确说了这是一个升序排列后的数组,经过了旋转,因此打乱了原先的排列顺序。这个题目和Leetcode33题和Leetcode81题非常类似,小伙伴们可以做完这个题目之后做一些另外两道。
旋转后可能出现三种情况,我们分别对其讨论,如下图所示。
因此最坏的情况下算法的**时间复杂度仍是$O(n)$,正常情况下算法的时间复杂度为$O(log(n))$,空间复杂度为$O(1)$**。
1 | #include<iostream> |
刷题总结
这类题目是二分查找的扩展题型,二分查找是算法的重点内容,也是面试笔试的常考知识点,希望小伙伴们能深刻理解。