旋转数组的最小值

数组的最小值"/>

旋转数组的最小值

文章目录

• 1 题目
• 2 思路
• • 2.1 思路1
  • 2.2 思路2
• 3 实现
• • 3.1 暴力
  • 3.2 二分查找

1 题目

将一个数组最开始的若干元素搬到数组的末尾，称之为数组的旋转。输入一个已排好序数组的一个旋转，求该旋转数组的最小元素。如，数组{3，4，，5，1，2}为有序数组{1，2，3，4，5}的一个旋转数组，该数组的最小值为1。

2 思路

2.1 思路1

暴力遍历数组，求出数组的最小元素。

时间复杂度：O(n)
空间复杂度：O(1)

2.2 思路2

将旋转后的数组看成两个升序的子序列，即查找一个元素（使用二分查找法），满足的条件为比相邻左边的元素小，也比相邻右边的元素小（如果存在的话）。

算法1详细（方便理解）：

• 用l指针指向第一个序列的第一个元素，用r指针指向第二个序列的最后一个元素；

• • 当l = mid时，r为最小元素（特殊处理当最小元素位于末尾的情况），例如{2,3,4,5,1}，此时最小元素为r指向的元素，而不是mid指向的元素;
• • 当元素满足比左边元素小，比右边元素小时，即为最小元素；
• • 如果中间指针mid（(l+r)/2）在第一个序列中（即A[mid] < A[l]），则要寻找的元素在后半段中，把l改为mid；
• • 如果中间指针mid第二个序列中(即A[mid]<A[r])，则要寻找的元素在前半中;

• 当l=r时，返回最小元素A[r]；否则，返回最小元素A[mid]。

算法2详细（上一种算法的改进版本）：

• 用l指针指向第一个序列的第一个元素，用r指针指向第二个序列的最后一个元素；

• • 如果中间指针mid（(l+r)/2）在第一个序列中（即A[mid] < A[l]），则要寻找的元素在后半段中，把l改为mid；
• • 如果中间指针mid第二个序列中(即A[mid]<A[r])，则要寻找的元素在前半中。

• 当l和r相邻时（此时mid=l），最小元素在r指向的元素。

时间复杂度：O(logn)
空间复杂度：O(1)

例如：原数组{1，2，3，4，5}，
旋转后的数组{2，3，4，5，1}，1比左边的5小，无右边的元素；
旋转后的数组{3，4，5，1，2}，1比左边的5小，比右边2小；
旋转后的数组{4，5，1，2，3}，1比左边的5小，比右边2小。

3 实现

3.1 暴力

#include<cstdio>int solution(int *A, int n){int ans = A[0];for(int i = 1;i < n;i++)if(A[i] < ans) ans = A[i];return ans;
}int main(){int A[] = {2,3,4,5,1};//int A[] = {3,4,5,1,2};//int A[] = {4,5,1,2,3};//int A[] = {5,1,2,3,4};printf("%d", solution(A, sizeof(A)/sizeof(A[0])));return 0;
}

3.2 二分查找

#include<cstdio>int solution(int *A, int n){int l = 0, r = n - 1, mid;while(l <= r){mid = (l + r)/2;printf("值   %d %d %d \n", A[l], A[mid], A[r]);printf("序号 %d %d %d \n", l, mid, r);//特殊处理最小元素位于最后一个的情况，例如2,3,4,5,1的情况，此时mid=l=3,r=4if(l == mid && A[r] < A[mid]) break;//如果比左边相邻的元素小//同时也比右边相邻的元素小（如果右边元素不存在，则和自己比较）if((A[mid] < A[mid-1] && A[mid] <= A[mid+1])) break;if(A[mid] < A[r]) r = mid;else l = mid;}return (l == mid)?A[mid+1]:A[mid];
}int solution2(int *A, int n){int l = 0, r = n - 1, mid;while(A[l] >= A[r]){if(r -l ==1){mid = r;break;}mid = (l + r)/2;printf("值   %d %d %d \n", A[l], A[mid], A[r]);printf("序号 %d %d %d \n", l, mid, r);if(A[mid] < A[r]) r = mid;else l = mid;}return A[mid];
}int main(){int A[] = {2,3,4,5,1};//int A[] = {3,4,5,1,2};//int A[] = {4,5,1,2,3};//int A[] = {5,1,2,3,4};printf("%d", solution(A, sizeof(A)/sizeof(A[0])));return 0;
}