|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
题目描述:
- 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
- ( 例如,数组 [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
- 来源:力扣(LeetCode)
- 链接:https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array
- 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码
1.自己想的
- class Solution {
- public:
- int findMin(vector<int>& nums) {
- int len = nums.size();
- if(len == 1) return nums[0];
- for(int i = 1; i < len; i++){
- if(nums[i] < nums[i-1]) return nums[i];
- }
- return nums[0];
- }
- };
复制代码
2.参照解题区写的【二分法】
- int findMin(vector<int>& nums) {
- int left = 0, right = nums.size()-1;
- while(left <= right){
- if(nums[right] >= nums[left])return nums[left];
- int mid = left + (right - left) /2;
- if(nums[mid] >= nums[left]){
- left = mid + 1;
- }
- else if(nums[mid] < nums[left]){
- right = mid;
- }
- }
- return -1;
- }
复制代码
最终得到的结果差不多 |
|