精华内容
下载资源
问答
  • 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{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。

    方法
    • 直接遍历,找到最小值。

    • 从前往后找,同时从后往前找

    • 二分查找。

    import java.util.ArrayList;
    public class Solution {
        public int minNumberInRotateArray(int [] array) {
        
            if (array.length == 0) {
                return 0;
            } 
            
             if(array.length==1){
                return array[0];
            }
           
            for (int i = 0; i < array.length; i++) {
                if (array[i] > array[i + 1]) {
                    return array[i + 1];
                }
            }
            return 0;
          
        }
    }
    
    import java.util.ArrayList;
    public class Solution {
        public int minNumberInRotateArray(int [] array) {
        
            if (array.length == 0) {
                return 0;
            } 
            
             if(array.length==1){
                return array[0];
            }
           
            for (int i = 0; i < array.length; i++) {
                
                //从前往后找
                if (array[i] > array[i + 1]) {
                    return array[i + 1];
                }
                
                //从后往前找
                if (array[array.length - 1 - i] < array[array.length - 2 - i]) {
                    return array[array.length - 1 - i];
                }
            }
            return 0;
          
        }
    }
    
    import java.util.ArrayList;
    public class Solution {
        public int minNumberInRotateArray(int [] array) {
        
            if (array.length == 0) {
                return 0;
            } 
            
             if(array.length==1){
                return array[0];
            }
           
           int first = 0;
           int last = array.length - 1;
    
            while (first < last) {
               int mid =  first + (last - first)  / 2;
               //中间元素大于最后元素,最小值在右区间
               if (array[mid] > array[last]) {
                 first = mid + 1;
                   //中间元素小于最后元素,最小值在左区间
               } else if (array[mid] < array[last]) {
                   last = mid;
                    //相等无法确定区间,但是可以把后指针前移
               } else {
                    last--;
               }
            }
            return array[first];
              
        }
    }
    
    展开全文
  • 输入一个排好序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为1。思路这道题最直观的解法并不难。从头到尾遍历数组一次,就能找出最小的元素,...

    问题

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

    思路

    这道题最直观的解法并不难。从头到尾遍历数组一次,就能找出最小的元素,时间复杂度显然是O(n)。但这个思路没有利用输入数组的特性。既然有时间复杂度更小的算法,我们容易想到二分查找,因为它的时间复杂度为O(logn)。这个问题是否可以运用二分查找呢?答案是肯定的。观察一下数组的特性,首先递增(称为递增a),然后突然下降到最小值,然后再递增(称为递增b)。当然还有一种特殊情况,就是数组递增,中间没有下降,即旋转元素个数为0。

    一般解法:找到中间下标,如果数组开始值小于中间下标对应的值,则表示中间下标属于第一个第一个递增,另开始下标等于中间下标,相反,如果中间下标对应的值小于结尾值,则表明,中间下标输入第二个递增,另结尾下标等于中间下标。直到开始下标和结尾下标相邻。

    特殊情况:旋转个数为0,例如{1,2,3,4,5},则可以通过第一个值小于最后一个值判断,直接输出第一个值。

    packageoffer008;importjava.util.Scanner;/*** @Title: Main.java

    * @Package: offer008

    * @Description 旋转数组的最小数字

    *@authorHan

    * @date 2016-4-18 上午10:39:35

    *@versionV1.0*/

    public classMain {public static voidmain(String[] args) {

    Scanner scanner= newScanner(System.in);int[] arr = null;int count = 0;while(scanner.hasNext()){//输入数组的大小

    count =scanner.nextInt();

    arr= new int[count];//输入数组

    for(int i = 0; i < count; i++){

    arr[i]=scanner.nextInt();

    }

    System.out.println(min(arr));

    }

    }/*** @Description 得到旋转数组中的最小值

    *@authorHan

    *@paramarr

    *@returnmin*/

    private static int min(int[] arr){//判断数组是否为空,长度是否为0

    if(arr == null || arr.length == 0){throw new RuntimeException("Error Input");

    }//头下标

    int startIndex = 0;//尾下标

    int endIndex = arr.length - 1;//中间下标

    int middleIndex = 0;//如果数组中的第一个值小于了最后一个值,则表明该数组为一个递增数组,直接输出第一个元素即可

    while(arr[startIndex] >=arr[endIndex]){//若该startIndex和endIndex相邻成立则表示endIndex指向的数字为最小值

    if(endIndex - startIndex == 1){

    startIndex=endIndex;break;

    }

    middleIndex= (startIndex + endIndex) / 2;//如果三个值相等,类似于1 0 1 1 1 1,则需要需要通过顺序查找出最小值

    if(arr[middleIndex] == arr[startIndex] && arr[middleIndex] ==arr[endIndex]){returnminByOrder(arr, startIndex, endIndex);

    }//若中间值大于startIndex指向的值,则移动startIndex到中间值

    if(arr[middleIndex] >=arr[startIndex]){

    startIndex=middleIndex;

    }else if(arr[middleIndex] <=arr[endIndex]){

    endIndex=middleIndex;

    }

    }returnarr[startIndex];

    }/*** @Description 顺序查找出最小值

    *@authorHan

    *@paramarr

    *@paramstartIndex

    *@paramendIndex

    *@return

    */

    private static int minByOrder(int[] arr, int startIndex, intendIndex) {int min =arr[startIndex];for(int i = startIndex + 1; i <= endIndex; i++){if(arr[i]

    min=arr[i];

    }

    }returnmin;

    }

    }

    结果

    a8a36abcdb8d29bd7ee29f09ef7cd395.png

    展开全文
  • 问题:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转,输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素,例如数组{3,4,5,1,2}为数组{1,2,3,4,5}的一个旋转,该数组的最小值为1。...

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

    解题思路:一个递增数组经旋转后分为两部分,它们都是递增的数组,第一个子数组的第一个元素不小于第二个子数组的最后一个元素,我们要寻找的是第一个子数组最后一个元素的下一个元素或第二个子数组的第一个元素。利用二分查找法,设有两个指针分别指向旋转数组的第一个和最后一个元素,设为left和right,找到两个指针的中间元素mid,如果它不小于第一个元素,则说明这个中间元素位于第一个递增子序列,我们要找的元素在这个中间元素的后面,此时将指向第一个元素指针left置为mid;如果它不大于最后一个元素,则说明这个中间元素位于第二个递增子序列,我们要找的元素在这个中间元素的前面,此时将指向最后一个元素的指针right置为mid。接下来递归调用该函数,最后left将指向第一个递增子序列的最后一个元素,right将指向第二个递增子序列的第一个元素,也即我们要寻找的元素,此时right-left==1。

    根据上述解题思路写出的代码如下:

    int Min(int* numbers,int length){

    int left = 0;

    int right = length-1;

    while(right-left>1){

    int mid = (left+right)/2;

    if(numbers[mid] >= numbers[left])

    left = mid;

    if(numbers[mid] <= numbers[right])

    right = mid;

    }

    return numbers[right];

    }

    但是上述写出的代码在某些情况下会遇到问题,如果该旋转数组是由原递增数组将最开始的0个元素移到数组末尾,那么将出现问题,如{1,2,3,4,5}找到的将是元素3。问题在于此时第一个子数组的第一个元素小于第二个子数组的最后一个元素,所以我们要对代码进行修改,修改后的代码如下:

    int Min(int* numbers,int length){

    int left = 0;

    int right = length-1;

    int mid = left;

    while(numbers[left] >= numbers[right]){

    if(right-left == 1){

    mid = right;

    break;

    }

    int mid = (left+right)/2;

    if(numbers[mid] >= numbers[left])

    left = mid;

    if(numbers[mid] <= numbers[right])

    right = mid;

    }

    //注意此时返回的是最中间元素的值,而不是numbers[right],是为了兼容第一个元素时最小值的情况

    return numbers[mid];

    }

    继续寻找特殊情况,我们发现如果是类似于如下的数组{1,0,1,1,1}或{1,1,1,0,1},第一个元素、最后一个元素、中间元素均相等,此时我们无法判断中间的元素时位于第一递增子序列({1,1,1,0,1})还是第二递增子序列({1,0,1,1,1}),此时我们只能遍历该序列从中找到最小值。修改后的代码如下:

    int Min(int* numbers,int length){

    int left = 0;

    int right = length-1;

    int mid = left;

    while(numbers[left] >= numbers[right]){

    if(right-left == 1){

    mid = right;

    break;

    }

    int mid = (left+right)/2;

    if(numbers[mid] == numbers[left] && numbers[mid] == numbers[right]){

    return finMin(numbers,left,right);

    }

    if(numbers[mid] >= numbers[left])

    left = mid;

    if(numbers[mid] <= numbers[right])

    right = mid;

    }

    return numbers[mid];

    }

    int findMid(int* numbers,int left,int right){

    int min = numbers[left];

    for(int i = left+1; i <= right; i++){

    if(numbers[i] < min)

    min = numbers[i];

    }

    return min;

    }

    展开全文
  • 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。示例1输入[3,4,5,1,2]返回值1学习一下大佬的思路(学到一个知识点:java位移操作符>> ...

    题目描述

    把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。

    输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。

    NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

    示例1

    输入

    [3,4,5,1,2]

    返回值

    1

    学习一下大佬的思路(学到一个知识点:java位移操作符>> 右移一位相当于乘二操作):

    public class Solution {

    public int minNumberInRotateArray(int[] array) {

    int i = 0, j = array.length - 1;

    while (i < j) {

    if (array[i] < array[j]) {//所有数都是相同的情况

    return array[i];

    }

    int mid = (i + j) >> 1; // >> java位移操作符,左移运算是将二进制位串向左移动n位,相当于除2操作,低位补0;右移运算是将二进制位串向右移动n位 相当于乘2

    if (array[mid] > array[i]) {//旋转后的数组最小值在右侧区域

    i = mid + 1; //在右边找

    } else if (array[mid] < array[j]) {//左侧区域

    j = mid;

    } else i++;

    }

    return array[i];

    }

    }

    贴一下我的垃圾思路,找一找自己的问题:

    import java.util.ArrayList;

    public class Solution {

    public int minNumberInRotateArray(int [] array) {

    if(array.length==0){

    return 0;

    }

    int i=0;

    int j=array.length-1;

    int mid=j/2;

    int max;

    while(array[mid]

    if(array[i]>array[mid]){

    mid=mid/2;

    }else{

    i=mid;

    mid=(i+j)/2;

    }

    }

    return array[mid];

    }

    }

    最后是程序运行超时。算法效率太低而且循环条件有问题,,,还要继续刷题啊。

    展开全文
  • return rotateArray[length-1] 人生苦短,我用Python 发表于 2016-08-27 14:51:27 回复(30) 13 public class Solution { /* * 传进去旋转数组,注意旋转数组的特性: * 1.包含两个有序序列 * 2.最小数一定位于第二...
  • 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 解题思路:采取栈存取...
  • /*** 找到旋转数组最小值* 由于部分有序,借用二分查找思想.三个游标index1,index2,indexMid* @author yanjie**/public class MinReverse {static int[] data = {5,6,7,8,9,1,2,3,4};//static int[] data = {1,0,1...
  • 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 一、Python: 1.1 直接...
  • 输入一个递增排序数组的一个旋转,输出旋转数组最小值。 示例: 数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转 该数组的最小值为1。 答案: 一般情况 {3,4,5,1,2},二分查找 特殊情况一 : {1,1,1,0,1}或{1,0,1,1...
  • 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 import java.util....
  • 输入一个递增排序的数组的一个旋转输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。思路:1.直接遍历一次数组,...
  • 【编程题】旋转数组最小值Java实现) 题目来源 剑指offer第六题 https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&tqId=11159&rp=1&ru=/ta/coding-interviews&qru=...
  • 旋转数组的最小数字标成了简单 下面我们先看中等题153: 题目描述:假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。 ...
  • 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{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。 又例如{1,0,1,1,1}和{1,1,1,0,1}都可以看成是递增排序数组{0,1,1,1,1}的...
  • 输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。可以借助二分查找法的...
  • 剑指Offer06 Java 旋转数组最小值 package offer6; /** * 把一个数组最开始的若干个元素搬到数组的末尾, * 我们称之为数组的旋转。 * 输入一个非递减排序的数组的一个旋转, * 输出旋转数组的最小元素。 *...
  • 旋转数组最小值

    2019-08-18 10:36:56
    输入一个排好序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为1。 思路及解答 import java.util.Scanner; import java.io.*; public class.....
  • * 找到旋转数组最小值 * 由于部分有序,借用二分查找思想.三个游标index1,index2,indexMid * @author yanjie * */ public class MinReverse { static int[] data = {5,6,7,8,9,1,2,3,4}; //static int[] ...
  • 旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 思路: 1.直接遍历一次数组,即可得出最小值。时间复杂度O(n...
  • 题目输入一个递增排序数列的一个旋转,输出旋转数组最小值算法: 局部有序 二分查找 特殊情况 {1,1,1,0,0,1,1} 无法区分哪个部分已经排序,只能把首部指针向前移动一位。 复杂度o(lgN)import java.util.*;...
  • 已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到: 若旋转 4 次,则可以得到 [4,5,6,7,0,1,2] 若旋转 4 次,则可以得到 ...
  • 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{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。 import java.util....
  • * 题目:旋转数组的最小数字 * 把一个数组最开始的若干个元素搬到数组的末尾,我们 * 称之为数组的旋转。输入递增排序的数组的一个旋转, * 输出旋转数组的最小元素。 * @author solomon * */ ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 521
精华内容 208
关键字:

旋转数组最小值java

java 订阅