描述
有一个长度为 n 的非降序数组,比如[1,2,3,4,5],将它进行旋转,即把一个数组最开始的若干个元素搬到数组的末尾,变成一个旋转数组,比如变成了[3,4,5,1,2],或者[4,5,1,2,3]这样的。请问,给定这样一个旋转数组,求数组中的最小值。
示例
输入:
[3,4,5,1,2]
返回值:
1
思路
1暴力求解,谁小把谁存放在min变量中
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int Min(int* arr, int sz)
{
int min = *arr;//存放第一个
for (int i = 1; i < sz; i++)
{
if (*(arr + i) < min)
{
min = *(arr + i);
}
}
return min;
}
int main()
{
int arr[] = { 4,5,1,2,3 };
int sz = sizeof(arr) / sizeof(arr[0]);
int ret=Min(arr, sz);
printf("%d", ret);
return 0;
}
核心代码模式
/**
*
* @param rotateArray int整型一维数组
* @param rotateArrayLen int rotateArray数组长度
* @return int整型
*/
int minNumberInRotateArray(int* rotateArray, int rotateArrayLen ) {
int min=*rotateArray;
for(int i=1;i<rotateArrayLen;i++)
{
if(*(rotateArray+i)<min)
{
min=*(rotateArray+i);
}
}
return min;
}
2采用二分法来解决,需要考虑三种情况:
(1)array[mid] > array[high]:
出现这种情况的array类似[3,4,5,6,0,1,2],此时最小数字一定在mid的右边。
low = mid + 1
(2)array[mid] == array[high]:
出现这种情况的array类似 [1,0,1,1,1] 或者[1,1,1,0,1],此时最小数字不好判断在mid左边
还是右边,这时只好一个一个试 ,
high = high - 1
(3)array[mid] < array[high]:
出现这种情况的array类似[2,2,3,4,5,6,6],此时最小数字一定就是array[mid]或者在mid的左
边。因为右边必然都是递增的。
high = mid
注意这里有个坑:如果待查询的范围最后只剩两个数,那么mid 一定会指向下标靠前的数字
比如 array = [4,6]
array[low] = 4 ;array[mid] = 4 ; array[high] = 6 ;
如果high = mid - 1,就会产生错误, 因此high = mid
但情形(1)中low = mid + 1就不会错误
标签:offer,int,mid,旋转,high,low,数组,array,rotateArray From: https://blog.51cto.com/u_15501985/6089160
/**
*
* @param rotateArray int整型一维数组
* @param rotateArrayLen int rotateArray数组长度
* @return int整型
*/
#include <stdlib.h>
int minNumberInRotateArray(int* rotateArray, int rotateArrayLen ) {
int low=0;
int high=rotateArrayLen-1;
while(low<high)
{
int mid=low+(high-low)/2;
if(rotateArray[mid]>rotateArray[high])
{
low=mid+1;
}
else if(rotateArray[mid]==rotateArray[high])
{
high=high-1;
}
else
{
high=mid;
}
}
return rotateArray[low];
}