鱼C论坛

 找回密码
 立即注册
查看: 2011|回复: 0

[技术交流] C++刷leetcode(153. 寻找旋转排序数组中的最小值)

[复制链接]
发表于 2020-4-27 10:36:56 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
题目描述:
  1. 假设按照升序排序的数组在预先未知的某个点上进行了旋转。

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

  3. 请找出其中最小的元素。

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

  5. 示例 1:

  6. 输入: [3,4,5,1,2]
  7. 输出: 1
  8. 示例 2:

  9. 输入: [4,5,6,7,0,1,2]
  10. 输出: 0

  11. 来源:力扣(LeetCode)
  12. 链接:https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array
  13. 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码




1.自己想的
  1. class Solution {
  2. public:
  3.     int findMin(vector<int>& nums) {
  4.         int len = nums.size();
  5.         if(len == 1) return nums[0];
  6.         for(int i = 1; i < len; i++){
  7.             if(nums[i] < nums[i-1]) return nums[i];
  8.         }
  9.         return nums[0];

  10.     }
  11. };
复制代码


2.参照解题区写的【二分法】
  1. int findMin(vector<int>& nums) {
  2.         int left = 0, right = nums.size()-1;
  3.         while(left <= right){
  4.             if(nums[right] >= nums[left])return nums[left];
  5.             int mid = left + (right - left) /2;
  6.             if(nums[mid] >= nums[left]){
  7.                 left = mid + 1;
  8.             }
  9.             else if(nums[mid] < nums[left]){
  10.                 right = mid;
  11.             }
  12.         }
  13.         return -1;

  14.     }
复制代码



最终得到的结果差不多
捕获.PNG

本帖被以下淘专辑推荐:

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-6 15:58

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表