讨论/技术交流/关于每日一题旋转数组的刷题建议思考/
关于每日一题旋转数组的刷题建议思考

最近连续三天的每日一题都是关于旋转数组的查找问题:
1. 搜索旋转排序数组
2. 寻找旋转排序数组中的最小值
3. 寻找旋转排序数组中的最小值 II

官方题解包括一些大佬们的解答中,二分查找为主要方法,不需要再赘述。
但是我觉得,应该不止我一个人,会走捷径这样完成这三个题目:

class Solution {
public:
    int findMin(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        return nums[0];
    }
};

那么这个题目的意义何在呢?
我们知道上述代码块的时间复杂度为O(n),而二分查找的时间复杂度为O(logn).
在刷题的时候,我们可以留意题目描述下面的进阶和提示信息,可以更好的达到刷题的效果。
这样我们才能学习不同的算法和思想,以及不同算法的区别优劣。

除此之外,可能会有部分人不理解为什么二分查找的时间复杂度为O(logn)?
可以按照下面的方法进行分析:
我们都知道二分查找在最坏的情况下依次是n/2,n/4,n/8......一直到1为止。
然后,意思就是要循环多少次才能查找到目标数呢,我们假设是x次。
然后我们可以观察到分母是每次都乘以1/2,分子不变,所以可以根据题意列出下面等式:
n(1/2)^x = 1,解出x=log2(n),省略底数,也就是O(logn)。

如果有什么错误,希望大家谅解。

1

二分没有最好与最坏之分,在区间没有减到一之前请不要停止循环。
原因是如果在循环中判断大于、等于、小于三种情况,会增大编码复杂度,虽然在一些情况下可以减少循环次数,但是会增大单次循环的常数,并不能有效起到加快速度的作用。最重要的一点:二分的路径分支七零八落,不方便统一管理。

展开全部 6 讨论