【题解】旋转数组的最小数字、比较版本号

旋转数组的最小数字

题目链接：旋转数组的最小数字

解题思路1：遍历求最小值

代码如下：

    int minNumberInRotateArray(vector<int> rotateArray) {int min = rotateArray[0];for(auto const& e: rotateArray){if(e < min){min = e;}}return min;}

解题思路2：比大小，最小的值一定是从数组最大值开始减小的那个值，也就是说第一次不是递增的那个值就是最小值，另一种情况是数组的第一个值，比如[1,2,2,2,2]这种情况

代码如下：

    int minNumberInRotateArray(vector<int> rotateArray) {for(int i=0; i<rotateArray.size()-1; ++i){if(rotateArray[i+1] < rotateArray[i])return rotateArray[i+1];}return rotateArray[0];}

解题思路3：二分

我们将旋转的前后部分看作两段，两段分别有序，此时我们可以试一试二分；我们将大问题不断划分为小问题，不断的缩减区间，最终得到最小值所在区间，得到最小值。

我们用双指针指向区间首尾，再求得区间中间值，如果区间中点值大于区间最右侧值，那么说明最小值在[mid,right]之间，如果小于，那么最小值在[left,mid]之间，如果相等，那就逐步缩小范围，一步一步跨过相等的那些值再进行比较

代码如下：

    int minNumberInRotateArray(vector<int> rotateArray) {int left = 0;int right = rotateArray.size() - 1;while(left < right){int mid = (left + right) / 2;if(rotateArray[mid] > rotateArray[right]){left = mid + 1;}else if(rotateArray[mid] == rotateArray[right]){right--;}else {right = mid;}}return rotateArray[left];}

比较版本号

题目链接：比较版本号

解题思路：双指针

我们用点来对版本号字符串进行分割，比较这两个版本号，直接使用双指针来进行比较，两个指针分别指向两个字符串进行比较

同时，由于前导零不参与比较，我们不知道数字前面有多少个前导零，所以还是将字符串转化为数字比较更方便

代码如下：

    int compare(string version1, string version2) {int n1 = version1.size();int n2 = version2.size();int i = 0;//version1的指针int j = 0;//version2的指针while(i < n1 || j < n2){long long num1 = 0;while(i < n1 && version1[i] != '.'){num1 = num1*10 + (version1[i]-'0');i++;}i++;long long num2 = 0;while(j < n2 && version2[j] != '.'){num2 = num2*10 + (version2[j]-'0');j++;}j++;if(num1 > num2) return 1;if(num1 < num2) return -1;}return 0;}

解题思路2：分割后比较

以点为间隔，将字符串进行分割，分割转化为数字存放进数组，再依次取出数组中的元素进行一一对比，得出结果

代码如下：

    //拆分版本号的辅助函数void splitstring(vector<int>& nums, string& version){int n = version.size(), num = 0;for(int i=0; i<n; ++i){if(version[i] == '.'){nums.push_back(num);num = 0;}else{num = num*10 + (version[i]-'0');}}nums.push_back(num);//最后一段数字}int compare(string version1, string version2) {vector<int> nums1, nums2;splitstring(nums1, version1);splitstring(nums2, version2);int n1 = nums1.size();int n2 = nums2.size();int p1 = 0, p2 = 0;for(int i=0; i<max(n1,n2); ++i){p1 = i < n1 ? nums1[i] : 0;p2 = i < n2 ? nums2[i] : 0;if(p1 > p2) return 1;if(p1 < p2) return -1;}return 0;}