如何查看网站是否开启gzip/seo算法是什么

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

解题思路：

思路一：数组中求解最小值，用暴力查找（顺序查找）的方法，时间复杂度o(n).

思路二：利用旋转数组的特点：

参考：https://www.cnblogs.com/klchang/p/7783386.html。

题目说明：输入的是一个非减排序的数组，也就是递增的有序数组，一般，对于有序数组的查找，我们首先想到的是二分法。而本题在有序数组的基础上，对数组进行了旋转，因此该递增的有序数组变成了两个递增的有序数组。中间的分隔点即是最小值所在的位置。

用两个指针low,high分别指向旋转数组的首尾，mid取他俩的算数平均，mid=(low+high)/2;

将两个指针所指的数分别和中间的数作比较，

如果mid所指的数比low指向的数大，说明mid所在的仍然是第一个递增数组，最小值在mid后面。则将low移动到mid的位置。

如果mid所指的数比high指向的数小，则说明mid所在的是第二个递增数组，最小值在mid前面。将high移动到mid的位置。

遍历终止的条件是如果两个指针走到了相邻的位置，则说明low走到了第一个数组的末尾，high走到了第二个数组的开头，此时high指向的就是最小值所在的位置。

其次，特殊情况，就是当首尾指针指向的元素和中间元素相等，此时无法遍历。只能采用顺序查找的方法。

代码：

做题时注意临界条件：都去等号

import java.util.ArrayList;
public class Solution {public int minNumberInRotateArray(int [] array) {if(array.length==0||array==null){return 0;}int low=0;int high=array.length-1;int min=array[low];int mid=0;//当数组发生旋转while(array[low]>=array[high]){//当两个指针挨着时，p2指向的就是最小的数了if(high-low==1){min=array[high];break;}mid=(low+high)/2;if(array[low]==array[mid]&&array[mid]==array[high]){min=minInOrder(array,low,high);}if(array[low]<=array[mid]){low=mid;	}else if(array[mid]<=array[high]){high=mid;}}return min;}private int minInOrder(int[] array, int low, int high) {// TODO Auto-generated method stubint min=array[low];for (int i = 0; i < high; i++) {if(min>array[i]){min=array[i];}			}return min;}
}

实现2：

思路同下leetcode

public class Solution {public int minNumberInRotateArray(int [] array) {if(array==null||array.length==0) return 0;int low=0,high=array.length-1;while(low<high){int mid=(low+high)/2;if(array[low]==array[mid]&&array[mid]==array[high]){return findMin(array,low,high);}else if(array[mid]<array[high]){high=mid;}else{low=mid+1;}}return array[low];}private int findMin(int[] array,int low,int high){int min=array[low];for(int i=low+1;i<=high;i++){if(array[i]<min){min=array[i];}}return min;}
}

 

另，本题与leetcode153. Find Minimum in Rotated Sorted Array是相同的思路，但是由于假设条件不一样，所以实现略有不同。

leetcode中，旋转数组中不存在重复的数，因为我们不需要考虑相等的情况。直接用两个指针遍历即可。

实现：（实现时，必须先判断右边，因为如果先判断左边，超过最小的数之前arr[left]<arr[mid],超过之后仍然满足这个条件）

class Solution {public int findMin(int[] nums) {if(nums==null||nums.length==0){return 0;}int left=0,right=nums.length-1,mid=0;while(left<right){mid=(left+right)/2;if(nums[mid]<nums[right]){//必须先判断右边right=mid;}else{left=mid+1;}}return nums[left];}
}