首页 > 其他分享 >153. 寻找旋转排序数组中的最小值

153. 寻找旋转排序数组中的最小值

时间:2023-10-02 14:55:40浏览次数:34  
标签:153 nums int mid 旋转 最小值 数组 排序 size

已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到:
若旋转 4 次,则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次,则可以得到 [0,1,2,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 ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

 

示例 1:

输入:nums = [3,4,5,1,2]
输出:1
解释:原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。

代码:


class Solution {
public:
    int findMin(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];
        //找到旋转点
        int l = -1;
        int r = nums.size();
        while(l + 1 != r){
            int mid = l + (r - l)/2;
            if(nums[mid] >= nums[0]){
                l = mid;
            }
            else{
                r = mid;
            }
        }
        //如果旋转点在最后
        if(r == nums.size())   return nums[0];
        return nums[r];
    }
};

标签:153,nums,int,mid,旋转,最小值,数组,排序,size
From: https://www.cnblogs.com/lihaoxiang/p/17739927.html

相关文章

  • 插入排序
    classSolution:definsertion_sort(lst):foriinrange(1,len(lst)):forjinrange(i,0,-1):iflst[j]<lst[j-1]:lst[j],lst[j-1]=lst[j-1],lst[j]else:......
  • 33. 搜索旋转排序数组
    整数数组nums按升序排列,数组中的值互不相同。在传递给函数之前,nums在预先未知的某个下标k(0<=k<nums.length)上进行了旋转,使数组变为[nums[k],nums[k+1],...,nums[n-1],nums[0],nums[1],...,nums[k-1]](下标从0开始计数)。例如,[0,1,2,4,5,6,7]在下标3处经......
  • 常见排序的python实现
    常见排序的python实现importnumpyasnpimporttimeitimportmatplotlib.pyplotasplt##生成测试序列defGenerateArray(n,N=1000):orginArray=np.random.randint(N,size=n).tolist()returnorginArrayorginArray=GenerateArray(20)print(orginArray)......
  • 34. 在排序数组中查找元素的第一个和最后一个位置
    给你一个按照非递减顺序排列的整数数组nums,和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值target,返回[-1,-1]。你必须设计并实现时间复杂度为O(logn)的算法解决此问题。示例1:输入:nums=[5,7,7,8,8,10],target=8......
  • Go每日一库之153:categraf (数据采集 Agent)
    简介Categraf是夜莺监控的默认数据采集Agent,主打开箱即用和all-in-one,同时支持对metrics、log、trace的收集,由夜莺监控核心开发团队开发。Categraf的代码托管在两个地方:中国计算学会确实开源平台:https://www.gitlink.org.cn/flashcat/categrafGithub:https://github.com/......
  • Go 1.19 排序算法
    插入排序(InsertionSort)插入排序是一种简单直观的排序算法,它的基本思想是将待排序的元素插入到已经排好序的序列中,从而得到一个新的有序序列。插入排序的具体过程如下:从第一个元素开始,认为它已经是有序的序列。取出下一个元素,在已经排序的序列中从后向前扫描。如果已经排序的......
  • 创建一个二叉排序树(Binary Search Tree)
    一、二叉排序树的定义左子树所有结点的值均小于根结点的值右子树所有结点的值均大于根节点的值左子树和右子树也是二叉排序树1.二叉排序树的结点结构typedefstructBSTNode{ /*二叉排序树的结点结构*/ intvalue; structBSTNode*left; structBSTNode*right;}BS......
  • 链表插入排序
    创建节点类publicclassNode{intn;Nodenext;}第1次推导publicclasstest{publicstaticvoidmain(String[]args){//新建节点Nodenode1=newNode();node1.n=2;Nodenode2=newNode();node......
  • 链表冒泡排序
    创建节点类publicclassNode{intn;Nodenext;}第1次推导publicclasstest{publicstaticvoidmain(String[]args){//新建节点Nodenode1=newNode();node1.n=9;Nodenode2=newNode();no......
  • 数组冒泡排序
    第1次推导publicclasstest{publicstaticvoidmain(String[]args){int[]ints={6,5,9,5};inttmp;if(ints[0]>ints[1]){tmp=ints[0];ints[0]=ints[1];ints[1]=tmp;}......