大家好，又见面了，我是全栈君。
题目：
一个递增的整形数组，如今的操作是每次从数组的开头取出一个元素放在数组的末尾。连续n次这种操作后得到一个新的数组，
一个递增的整形数组，如今的操作是每次从数组的开头取出一个元素放在数组的末尾。连续n次这种操作后得到一个新的数组，
如今把这个数组给你，请求出最少移动的次数。
解析：
1 最easy想到的方法就是依次遍历这个数组，找到最小值的位置，这种时间复杂度就是O(n)。
2 考虑到事先是排好序的，所以我们能够使用二分查找法来实现这个操作，仅仅只是是这个二分查找法是传统二分查找法的变种。
这里我们仅仅要考虑下面3种情况。
<1>数组先递增再递减，中值大于左值，那么此时的最小值就处于数组的右半部。
<2>数组先递增再递减，中值小于左值，那么此时的最小值就处于数组的左半部。
<3>数组单调递增，此时的最小值就是数组的首元素。
3 程序实现
依据解析中2的思想，採取二分查找法的程序例如以下所看到的：
#include <iostream>
using namespace std;
int getInvertNumber(int arr[],int nLength);
void main()
{
int arr[] = {1,2,3,4,5,6,7,8,9};
int brr[] = {1,3,4,6,8,9};
int sb = getInvertNumber(brr,sizeof(brr)/sizeof(brr[0]));
cout<<sb<<endl;
}
int getInvertNumber(int arr[],int nLength)
{
int nLeft = 0;
int nRight = nLength-1;
int nMid;
if(arr[nLeft]<arr[nRight])
return 0;
while(nLeft<nRight)
{
nMid = ( nLeft + nRight ) / 2;
if(arr[nMid]>arr[nLeft])
nLeft = nMid;
else
nRight = nMid;
}
return nLength -nMid-1;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116511.html原文链接：https://javaforall.net
