旋转数组的最小数字(实现和思路)

KLQ 2020-05-13 10:01:19 java常见问答 7601

下面给大家带来的实例是和旋转数组的最小数字相关的内容,一起来看看题目以及解题思路和代码实现吧!

题目:

将一个数组最开始的若干个元素搬到数组的末尾,我们把它叫做是数组的旋转。

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

例:

数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,这个数组的最小值是1。

NOTE:

给出的所有元素都大于0,假如数组大小为0,那么,就请返回0。

思路1

代码实现:

function minNumberInRotateArray(rotateArray) {
    var left = 0,
        length = rotateArray.length,
        right = length - 1,
        mid;
    if (length == 0) { return 0; }
    while (rotateArray[left] >= rotateArray[right]) {
        if (rotateArray[left] == rotateArray[right]) {
            // 对left去重,使其指向最后一个重复的数字
            for (var i = left; i < right; i++) {
                if (rotateArray[left] != rotateArray[i]) {
                    left =i-1;
                    break;
                }
            }
            // 对right去重,使其指向最前一个重复的数字
            for (var i = right; i > left; i--) {
                if (rotateArray[right] != rotateArray[i]) {
                    right = i+1;
                    break;
                }
            }
        }
 
        if (right - left <= 1) {
            mid = right;
            break;
        }
        // 四舍五入取整数,否则得到的就是小数,会报错;
        mid = Math.round(left + (right - left) / 2);
        if (rotateArray[mid] >= rotateArray[left]) {
            left = mid;
        } else {
            right = mid;
        }
    }
    return rotateArray[mid];
}

思路2

代码实现:

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
     if(array == null || array.length==0)
   return 0;
  int low = 0;
  int high = array.length-1;
  int mid = low;
  while(array[low]>=array[high]){
   if(array[low] == array[high]){
    for(int i=low;i
<array.length;i++){
     if(array[low]!=array[i]){
      low = i-1;
      break;
     }
    }
    for(int i=high;i>=0;i--){
     if(array[high]!=array[i]){
      high = i+1;
      break;
     }
    }
   }
   if(high-low<=1){
    mid = high;
    break;
   }
   mid = (low+high)/2;
   if(array[mid]>=array[low]){
    low = mid;
   }else if(array[mid]<=array[high]){
    high = mid;
   }
  }
  return array[mid];
    }
}

思路3:

非递减数组旋转之后最小值,也就是寻找分界点,分界点前后都是非递减数组,分界点后面的非递减数组比分界点前面的数组都要小,所以对旋转数组按顺序查找,当出现后一个数比前一个小时,这个数就是最小值,假如没有出现后一个数比前一个数小的情况,这说明这个数组所有的数都相等,返回数组第一个数就可以了。

注意考虑数组为空的情况,返回0

代码实现:

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

以上的代码实现仅供参考,希望可以帮助到大家,更多的实例,可以继续通过本站的java实例栏目来了解哦!

推荐阅读:

斐波那契数列(实现和思路)

二分法查找(思路和实现),二分法查找是什么?

二进制中1的个数(思路和实现)