题目
把一个数组最开始的若干个元素搬到数组末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素，例如，数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
分析
暴力法
我们不考虑任何特点，直接一次循环求解。
C
#include<stdio.h> #include<stdlib.h> int Min(int* n, int length) { int min = INT_MAX; int i = 0; for (i = 0; i < length; i++) { if (n[i] < min) { min = n[i]; } } return min; } int main() { int p[5] = { 3,4,5,1,2 }; int size = 5; int ret = Min(p, size); printf("最小值为：%d\n", ret); return 0; }
二分法
我们可以将这个旋转过后的数组，分成俩个递增子数组。
但是还存在一种特殊情况旋转后的数组和原数组相同
总共有俩种情况
旋转后数组与原数组不相同
旋转后数组与原数组相同
设置start、end指针分别指向数组左右俩边，然后选取中间值mid = ((end - start)>>1 + start),防止溢出。
我们先选start指针做判断位置：
n[start] < n[mid] 在情况一中，mid位于左递增子数组，在情况二中mid位于右递增数组，所以我们换判断点
选end指针做判断位置：
n[end] < n[mid] 在情况一中，mid位于左递增子数组。在情况二中，不存在这种
- n[end] > n[mid] 在情况一中，mid位于右递增子数组。在情况二中，mid位于右递增子数组
n[end] = n[[mid] 在情况一中，mid位于右递增子数组。在情况二中，mid位于右递增子数组。
C
#include<stdio.h> #include<stdlib.h> int Min(int* n, int length) { if (n == NULL || length <= 0) { perror(""); exit(EXIT_FAILURE); } int start = 0; int end = length - 1; while (start < end) { int mid = ((end - start) >> 1) + start; if (n[end] < n[mid]) { start = mid + 1; } else if (n[end] > n[mid]) { end = mid; } else { end--; } } return n[start]; } int main() { int n[10][5] = { {1,2,3,4,5}, {2,3,4,5,1}, {3,4,5,1,2}, {4,5,1,2,3}, {5,1,2,3,4}, {1,1,1,2,2}, {1,1,2,2,1}, {1,2,2,1,1}, {2,2,1,1,1}, {1,1,2,2,2}, }; int i = 0; for(i = 0; i< 10;i++) { int ret = Min(n[i],5); printf("min = %d\n", ret); } return 0; }
最坏情况就是{1，1，1，1，1}；相当于O(n)的时间复杂度，空间复杂度是常量O(1);
最好情况时间复杂度就是O(long2^N),空间复杂度是常量O(1);
我们也可以让n[end] = n[[mid] 相等时候直接遍历start到end 线性查找
#include<stdio.h> #include<stdlib.h> int Min(int* n, int length) { if (n == NULL || length <= 0) { perror(""); exit(EXIT_FAILURE); } int start = 0; int end = length - 1; while (start < end) { int mid = ((end - start) >> 1) + start; if (n[end] < n[mid]) { start = mid + 1; } else if (n[end] > n[mid]) { end = mid; } else { int m = start;//保存最小值小标 for (++start; start < end; ++start) { if (n[m] > n[start]) { m = start; } } return n[m]; } } return n[start]; } int main() { int n[10][5] = { {1,2,3,4,5}, {2,3,4,5,1}, {3,4,5,1,2}, {4,5,1,2,3}, {5,1,2,3,4}, {1,1,1,2,2}, {1,1,2,2,1}, {1,2,2,1,1}, {2,2,1,1,1}, {1,1,2,2,2}, }; int i = 0; for(i = 0; i< 10;i++) { int ret = Min(n[i],5); printf("min = %d\n", ret); } return 0; }
本章完！
