剑指offer——链表：旋转数组的最小数字

1、暴力

思路

先设一个变量存储数字的第一个元素，遍历整个数组，将每个元素与标准值进行比较，如果数组内的元素更小，将数组内元素替换标准值

代码

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param nums int整型vector * @return int整型*/int minNumberInRotateArray(vector<int>& nums) {// write code hereif(nums.size()==0)return 0;int min=nums[0];for(int i=1;i<nums.size();i++){if(min>nums[i]){min=nums[i];}}return min;}
};

2、二分法

思路

使用二分查找，与数组的最右侧节点进行比较

如果中间节点比最右侧节点小，说明最小值应该在中间节点的左侧；如果中间节点比最右侧节点大，说明最小值应该在中间值右侧；如果中间值和最右侧节点值相等，暂时因为重复节点，不能确定最小值位置

代码

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param nums int整型vector * @return int整型*/int minNumberInRotateArray(vector<int>& nums) {// write code here//使用二分查找int left=0;int right=nums.size()-1;while(left<right){int mid=(left+right)/2; //获取中间值if(nums[mid]<nums[right]){right=mid;}else if(nums[mid]>nums[right]){left=mid+1;}else{right--;}}return nums[left];}
};