首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >153. 寻找旋转排序数组中的最小值

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

作者头像
程序员小王
发布2023-03-28 09:10:29
6570
发布2023-03-28 09:10:29
举报
文章被收录于专栏:架构说架构说
153. Find Minimum in Rotated Sorted Array
1. 描述:

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

输入: [3,4,5,1,2]
输出: 1

示例 2:

输入: [4,5,6,7,0,1,2]
输出: 0
2.分析

期望:请找出其中最小的元素

第一次尝试: 直接遍历

描述:

最小值和每个元素比较一遍,

 比较次数 o(n)
 执行用时: 28 ms, 在Find Minimum in Rotated Sorted Array的C++提交中击败了2.89% 的用户

第二次尝试:减少比较次数

对一个数组进行折半拆分(至少3个元素)

如果是升序,第一就是最小值 两两比较:

世界杯一共进行64场,

其中分小组赛48场,1/8决赛8场,1/4决赛4场,半决赛两场,决三、四名比赛一场,冠亚军决赛一场.

比较 需要o(n-1) 没有减少呀!

执行用时: 4 ms, 在Find Minimum in Rotated Sorted Array的C++提交中击败了98.16% 的用户

3. c++
/**
   Time  complexity:T(n) = O(1) + T(n/2) = O(logn)
   Space complexity:o(1)
   查找逻辑跟索引位置切分的,根数据大小没关系,数据全部相等,也没有关系
   **/
   int find_min(vector<int>&nums,int start,int end){     
       if((end-start)<=1)
       {       return min(nums[start],nums[end]);    
       }        
       if (nums[end]>nums[start])
        {            
          return nums[start];
       }        
         int mid=(start+end)/2;        
        int left=find_min(nums,start,mid);       
        int right=find_min(nums,mid+1,end);        
        return min(left,right);   }   
    
4. go
/** 第一题 find-minimum-in-rotated-sorted-array
https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/description/
153. 寻找旋转排序数组中的最小值
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
请找出其中最小的元素。期望:请找出其中最小的元素
拦路虎:
1. 如果是完全升序  第一数字就是 ,
  旋转数值是升序(相邻的元素都是递增), 根本不知道抄那个方向移动?炸锅了。
  肯定没有那么容易赛。
2. 我想通过观察特点 怪点(2边元素都大于它)就是最小元素这个没问题,,需要至少4个元素判断 很容易越界。 i++。i--都比较复杂了
  还是回到问题1,
比较点【相邻元素】【边界元素】【变化点】都有缺陷
过程描述
随便寻找一个数字i,判断nums[i]是否为最小值
1 如果nums[i]>nums[end],说明nums[i]不是最小元素 ,最小元素在后面 ---> i+1
2.如哦nums[i]<nums[end],nums[end]不是最小元素,后面元素比当前元素i还大,这是升序 最小元素在前面  <---- i-1
 但是最后一个元素情况下 nums[end]可能是最小元素 i(这个)
3 如果 nums[i]==nums[end] 相等的话就舍去一个呀(这个遗漏了)
4 折半查找直到循环结束,范围缩小到最后一个元素 (这个不是一般能想到的,讨巧了,时候才知道,不是通用的方法 if 判断 watch结果是否越界)测试:
1 int{1, 2, 3, 4, 5, 6} 如果升序不需要排序 上面规则不在查找了 ok
2 {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}  ok
3.{3, 3, 1, 3} 完全错误的是
缺点:
1. 通过数字的大小有关系,
跟数字的内容有关系,需要很复杂的逻辑判断。 有点不是很好
find-minimum-in-rotated-sorted-array-ii case3的时候我代码完全不对了
2. 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 性能o(n)case1 寻找不到怎么办
别人的答案:
https://www.youtube.com/watch?v=P4r7mF1Jd50&t=3s
http://zxi.mytechroad.com/blog/divide-and-conquer/leetcode-153-find-minimum-in-rotated-sorted-array/
!!!!!!!!!
折半查找没有问题,但是元素比较出现了问题,无论怎么比较都不对,比较元素这个思路是错误的**/func findMin(nums []int) int {
   begin := 0
   end := len(nums) - 1
   mid := 0
   if nums[end] > nums[begin] {        //fmt.Println("sort array", nums[begin])
       return nums[begin]
   }    for begin < end {
       mid = (begin + end) / 2
       if nums[end] < nums[mid] {
           begin = mid + 1 //排除nums[mid]不是最小元素,最小元素在后面
       } else if nums[end] > nums[mid] {
           end = mid
       } else {
           end--
       }        //fmt.Println(begin, end, mid)
   }    return nums[begin]}
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-01-04,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Offer多多 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 153. Find Minimum in Rotated Sorted Array
  • 1. 描述:
  • 2.分析
  • 3. c++
  • 4. go
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档