精华内容
下载资源
问答
  • 旋转数组最小数字

    2020-08-04 22:17:56
    旋转数组最小数字 /*旋转数组最小数字(剑指offer、二分查找) * 题目描述:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 * 输入一个递增排序的数组的一个旋转,输出旋转数组的最小...

    旋转数组最小数字

    /*旋转数组最小数字(剑指offer、二分查找)
     * 题目描述:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
     * 			输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。
     * 解题思路:
     * 			题目要求找到最小元素,第一反应是排序,但数组基本有序直接排序浪费性能。
     * 			结合数据的特点前半部分递增,后半部分递减,从头开始遍历直到有元素小于前一个数.
     * 			上面一种思路的目的是要找到递增部分和递减部分的临界点该点的特性为大于前一个和后一个元素
     *			二分查找:
     *			声明p1指向查找区域的首元、p2指向查找区域的末元,mid指向当前查找元素。
     *			p1=1,p2=data.length,mid=(p1+p2)/2
     *			如果mid指向的数的左边的元素小于mid右边的元素也小于mid,返回mid下一个元素的值
     *			如果mid左边的元素小于mid右边的元素大于mid,p2=mid mid=(p2-p1)/2
     *			如果mid左边的元素大于mid右边的元素小于mid,p1=mid mid=(p2-p1)/2
     *			!!!这种解法失败,原因:测试数据中包含不旋转的数据,即完全有序的数组,这种情况不再存在上面思路的特征点!!!
     *题解思路:
     *			维持两个指针p1指向搜索区域的左边,p2指向搜索区域的右边,mid指向搜索区域的中间
     *			如果mid大于p1说明从p1到mid是递增的,最小值应该位于mid到p2,将p1指向mid。
     *			如果mid小于p1说明p1到mid是递减的,最小值就位于p1到mid中,将p2指向mid。
     *			当mid等于p1,无法判断p1到mid是增或减,遍历p1到p2取最小值
     *			
     * */
    public class XuanZhuanShuZuDeZuiXiaoShuZi {
    	public static void main(String[] args) {
    		XuanZhuanShuZuDeZuiXiaoShuZi_Solution2 solution = new XuanZhuanShuZuDeZuiXiaoShuZi_Solution2();
    		int[] numbers = {1,3,3};
    		System.out.println(solution.minArray(numbers));
    	}
    }
    
    class XuanZhuanShuZuDeZuiXiaoShuZi_Solution1 {
        public int minArray(int[] numbers) {
            int p1=0;
            int p2=numbers.length-1;
            int mid = (p1+p2)/2;
            while(mid!=p1&&mid!=p2) {
            	//如果mid大于左边的且大于右边的,返回mid右边的
            	if(numbers[mid]>=numbers[mid-1]&&numbers[mid]>=numbers[mid+1]) {
            		return numbers[mid+1];
            	}
            	//如果mid小于左边的且小于右边的,返回mid
            	if(numbers[mid]<=numbers[mid-1]&&numbers[mid]<=numbers[mid+1]) {
            		return numbers[mid];
            	}
            	//如果mid大于左边的 小于右边的,p2=mid、mid=(p1+p2)/2
            	if(numbers[mid]>=numbers[mid-1]&&numbers[mid]<=numbers[mid+1]) {
            		p2 = mid;
            		mid = (p1+p2)/2;
            		continue;
            	}
            }
            return numbers[mid];
        }
    }
    
    class XuanZhuanShuZuDeZuiXiaoShuZi_Solution2{
    	public int minArray(int[] numbers) {
    		int p1 = 0;
    		int p2 = numbers.length-1;
    		while(p1 != p2) {
    	//		System.out.println(numbers[p1]+" "+numbers[(p1+p2)/2]+" "+numbers[p2]);
    			if(numbers[(p1+p2)/2] > numbers[p2]) {
    	//			System.out.println("aa");
    				p1 = (p1+p2)/2+1;
    				continue;
    			}
    			if(numbers[(p1+p2)/2] < numbers[p2]) {
    	//			System.out.println("bb");
    				p2 = (p1+p2)/2;
    				continue;
    			}
    			if(numbers[(p1+p2)/2] == numbers[p2]) {
    				if(numbers[(p1+p2)/2]>numbers[(p1+p2)/2+1]) {
    	//				System.out.println("cc1");
    					p1 = (p1+p2)/2+1;
    					continue;
    				}else {
    					int temp = numbers[p1];
    					for(int i=p1;i<p2+1;i++) {
    						if(numbers[i]<temp) {
    							temp=numbers[i];
    						}
    					}
    					return temp;
    				}
    			}
    		}
    		return numbers[(p1+p2)/2];
        }
    }
    

     

    展开全文
  • 8. 旋转数组最小数字

    2020-08-19 00:59:11
    输入一个递增排序的数组的一个旋转,输出旋转数组最小元素。例如,数组[3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。 class Solution: def minArray(self, numbers: [int]) -> int: i, j = ...

    题目

    把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。  

    class Solution:
        def minArray(self, numbers: [int]) -> int:
            i, j = 0, len(numbers) - 1
            while i < j:
                m = (i + j) // 2
                if numbers[m] > numbers[j]: 
                    i = m + 1
                elif numbers[m] < numbers[j]: 
                    j = m
                else: 
                    j -= 1
            return numbers[i]
    class Solution {
    public:
        int minArray(vector<int>& numbers) {
            int low = 0;
            int high = numbers.size() - 1;
            while (low < high) {
                int pivot = low + (high - low) / 2;
                if (numbers[pivot] < numbers[high]) {
                    high = pivot;
                }
                else if (numbers[pivot] > numbers[high]) {
                    low = pivot + 1;
                }
                else {
                    high -= 1;
                }
            }
            return numbers[low];
        }
    };

    展开全文
  • 输入一个非递减排序的数组的一个旋转,输出旋转数组最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 function ...

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

    function minNumberInRotateArray(rotateArray)
    {
        // write code here
       
           var newArr = rotateArray.sort(function(a,b){return a-b;});
           return newArr[0];
        
    }
    
    展开全文
  • 输入一个非递减排序的数组的一个旋转,输出旋转数组最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 思路:若数组的长度...

    题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
    思路:
    1. 数组中不包含重复元素,例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。那么我们可以采用二分搜索的改进版本实现。
    2. 若数组的长度为0,则返回0。初始化三个指针left, right和mid,left指向数组的第一个元素,right指向数组的最后一个元素,mid初始化为0。因为数组是经过旋转的,此时旋转可能造成两种情况。第一种情况是:旋转位置为0,则相当于没有进行过旋转,且数组中不包含重复元素,若数组的长度为1,则会发生array[left] == array[right]的情况;另一种情况是:旋转的位置不为0,对于数组中没有重复的元素,则left指向左侧序列,right指向右侧序列,有array[left] > array[right]。
    3. 若right - left = 1,此时right指向的就是旋转数组的最小元素,则返回array[right],结束循环。
    4. 令mid = left + (right - left) / 2,则若array[mid] > array[left],则mid指向的元素左侧是有序的,旋转数组的最小值肯定在array[mid]的右侧,此时left = mid。
    5. 若array[mid] < array[right],此时array[mid]的右侧是有序的,旋转数组的最小值肯定在array[mid]的左侧,此时right = mid;
    6. 若数组没有被旋转,因为mid的初始值为0,直接返回第一个元素array[mid]。
    7. 若数组中有重复元素,比如对数组{0, 1, 1, 1, 1, 1}进行旋转则会得到{1, 1, 0 ,1, 1}。令poi = 0,逐个遍历数组,寻找当array[i + 1] < array[i] 时的旋转数组最小值,若不存在这种情况,返回array[poi],即第一个元素。

    public class Solution {
        //若数组中包含重复元素,则进行逐个遍历
        public int getPoi(int[] array){
            int poi = 0;
            if(array.length == 1){
                return array[0];
            }
            for(int i = 0; i < array.length; i++){
                if(array[i + 1] < array[i]){
                    poi = array[i + 1];
                    break;
                }
            }
            return poi;   
        }
    
        public int minNumberInRotateArray(int [] array) {
            if(array.length == 0){
                return 0;
            }
            int left = 0;
            int right = array.length - 1;
            int mid = 0;
            /**若数组中没有重复的元素,left在左侧序列,right在右侧序列,
                若数组反转位置%array.length != 0,则必有array[left] > array[right],左侧序列元素大于右侧序列元素
               若数组中有重复元素,则可能会发生array[left] == array[right]。
            **/
            while(array[left] >= array[right]){
                if(right - left == 1){
                    return array[right];
                }
                mid = left + (right - left)/2;
                //array数组中有重复元素,逐个遍历
                if(array[mid] == array[left] && array[mid] == array[right]){
                   getPoi(array);
                }
                //若array[mid] >= array[left],则mid的左侧是有序的,最小值在右侧;
                //若array[mid] = array[left],可能有两种情况,1. mid = left 2.数组中有重复元素
                if(array[mid] >= array[left]){
                    left = mid;
                }
                //mid的右侧是有序的,最小值在左侧
                if(array[mid] <= array[right]){
                    right = mid;
                }
            }
            //若数组是单调递增的,则返回第一个元素
            return array[mid];
        }
    }
    展开全文
  • 一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 ...
  • 输入一个非递减排序的数组的一个旋转,输出旋转数组最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 思路:使用二分查找...
  • 输入一个非减排序的数组的一个旋转,输出旋转数组最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 2.思路 因为所有的数据...
  • 输入一个非递减排序的数组的一个旋转,输出旋转数组最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 有序数组的查找...
  • 旋转数组最小数字 | 153. 寻找旋转排序数组中的最小值 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2]...
  • 今天做到旋转数字最小数字时,看到需要考虑的边界有些麻烦,因而分析总结一下。 旋转数组其实就是一个递增排序数组的旋转,例如{3,4,5,1,2}即为{1,2,3,4,5}的一个旋转数组旋转数组有一个特性:包含...
  • 输入一个非减排序的数组的一个旋转,输出旋转数组最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 总结:第一遍写 时取巧...
  • 2.不难发现,如果是一个正常的递增数组,数组最小的元素是第一个元素,数组最大的元素就是最后一个元素;当你把他旋转后,最大的元素就会在最小的数组元素的前面,以这两个元素(设为left和right)为边界,这个数组...
  • 不难发现,如果是这种情况,那么那个上升点的位置(本例中即是1),即是旋转数组最小数字。 那么我们再对问题进行推广 对于一个非朴素的旋转数组(包含重复数字,或没有元素旋转) 给出以下三个样例: ...
  • 输入一个非递减排序的数组的一个旋转,输出旋转数组最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 思路从代码能清楚地读...
  • 6. 旋转数组最小数字 &剑指 Offer 11. 旋转数组最小数字 题目描述 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 ...
  • 主要介绍了求解旋转数组最小数字的相关资料,需要的朋友可以参考下
  • 旋转数组最小数字 问题描述 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个...
  • 旋转数组最小数字

    2019-08-06 11:13:16
    旋转数组最小数字,即输入一个递增排序数组的一个旋转数组,输出旋转数组中的最小数字。例如,输入数组{3,4,5,1,2},输出1。{3,4,5,1,2}为{1,2,3,4,5}的旋转数组。 思路:最简单的做法就是不管...
  • 剑指offer ( 六 ):旋转数组最小数字 1.本题知识点    查找 2. 题目描述   把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 20,505
精华内容 8,202
关键字:

旋转数组的最小数字