题解 | #旋转数组的最小数字#

旋转数组的最小数字

https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba

解题思路

二分法。

  • 如果中点处的值大于右边界的值,则最小值在中点右边,更新左边的边界;
  • 如果中点处的值小于右边界的值,则最小值在中点的左边或者是中点,更新右边界的值;
  • 如果相等的话,则逐步向左减少右边界的值。
  • 最终返回结果即可。

复杂度

  • 时间复杂度为O(logn);
  • 空间复杂度为O(1)。

代码

Python

class Solution:
    def minNumberInRotateArray(self , nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1

        while left < right:
            mid = (right+left) // 2

            if nums[mid] > nums[right]:
                left = mid + 1
            elif nums[mid] == nums[right]:
                right -= 1
            else:
                right = mid

        return nums[left]

C++

class Solution {
public:
    int minNumberInRotateArray(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;

        while(left < right)
        {
            int mid = int((left+right) / 2);
            if(nums[mid] > nums[right])
            {
                left = mid+1;
            }
            else if(nums[mid] < nums[right])
            {
                right = mid;
            }
            else {
                right--;
            }
        }

        return nums[left];
    }
};

全部评论

相关推荐

04-25 18:13
五邑大学 Java
后来123321:大二两段实习太厉害了,我现在大二连面试都没有
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务