对网站建设 意见和建议,游戏链接点开即玩,整套vi设计都包含哪些,红网常德论坛发现还是数组这种最简单的编码才适合我#xff0c;遇到树#xff0c;链表这些真的是一头雾水#xff0c;自己也不知道怎么实现。言归正传#xff0c;该篇文章介绍如何求旋转数组的最小值#xff0c;求最大值可以适当改编即可。
什么是旋转数组呢#xff0c;就是将一个数…发现还是数组这种最简单的编码才适合我遇到树链表这些真的是一头雾水自己也不知道怎么实现。言归正传该篇文章介绍如何求旋转数组的最小值求最大值可以适当改编即可。
什么是旋转数组呢就是将一个数组的前几个元素和后面几个元素互换位置。例如原数组升序的数组为{0123456789}将其旋转后变为{5678901234}。如何求该数组的最小值呢有一种方法是直接按顺序比较但是这就体现不出旋转数组的特性了所以更好的解法应该是采用二分法来求得该数组的最小值。我们可以发现在旋转数组中9坐标的数都比它小右边的数也都比它小。我们设有2个指针左指针指向最左边的元素右指针指向最右边的元素。我们判断中间的元素和最左边元素的大小如果中间的数大于左指针指向的元素证明最小的数字在中间数字的右边。这样我们就可以缩小范围啦。
代码如下
#includeiostream
#includecstdlib
#include stack
#include stdio.h
#includetime.husing namespace std;int Min(int a[], int length)
{if (a nullptr || length 1) //如果出现数组中只有一个元素的就直接报错吧throw new exception(Invalid parameters);int left 0;int right length - 1;while (a[left] a[right]) {if (right left2) //数组中有2个或者三个元素最右边的元素都是最小的return a[right];int mid (left right) / 2;if (a[mid] a[left])left mid;else if (a[mid] a[right])right mid;}return a[right];
}int main()
{int a[] { 44,45,46,1,2,3,15,33,41 };int minMin(a, 6);cout min endl;system(pause);}不过很显然这种方法不是很完善的因为没有考虑一种比较特殊的情况就是数组中拥有重复元素的时候。比如数组{11101}{10111}。这种时候就只能选择顺序查找的办法啦。
改进代码如下
#includeiostream
#includecstdlib
#include stack
#include stdio.h
#includetime.husing namespace std;int MinInOder(int a[], int left,int right)
{int result a[left];for (int i left1; i right; i){if (a[i] result)result a[i];}return result;
}int Min(int a[], int length)
{if (a nullptr || length 1)throw new exception(Invalid parameters);int left 0;int right length - 1;while (a[left] a[right]){if (right left2)return a[right];int mid (left right) / 2;if (a[right] a[left] a[mid] a[right])return MinInOder(a, left,right);if (a[mid] a[left])left mid;else if (a[mid] a[right])right mid;}return a[right];
}int main()
{int a[] { 1,1,1,1,0,1,1,1,1 };int minMin(a, 6);cout min endl;system(pause);}
