首页 > 代码库 > 美团面试题:寻找数组置尾操作的最小值
美团面试题:寻找数组置尾操作的最小值
题目:
一个递增的整形数组,现在的操作是每次从数组的开头取出一个元素放在数组的末尾,连续n次这样的操作后得到一个新的数组,
现在把这个数组给你,请求出最少移动的次数。
解析:
1 最容易想到的方法就是依次遍历这个数组,找到最小值的位置,这样的时间复杂度就是O(n)。
2 考虑到事先是排好序的,所以我们可以使用二分查找法来实现这个操作,只不过是这个二分查找法是传统二分查找法的变种。
这里我们只要考虑以下3种情况。
<1>数组先递增再递减,中值大于左值,那么此时的最小值就处于数组的右半部。
<2>数组先递增再递减,中值小于左值,那么此时的最小值就处于数组的左半部。
<3>数组单调递增,此时的最小值就是数组的首元素。
3 程序实现
根据解析中2的思想,采取二分查找法的程序如下所示:
一个递增的整形数组,现在的操作是每次从数组的开头取出一个元素放在数组的末尾,连续n次这样的操作后得到一个新的数组,
现在把这个数组给你,请求出最少移动的次数。
解析:
1 最容易想到的方法就是依次遍历这个数组,找到最小值的位置,这样的时间复杂度就是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; }
美团面试题:寻找数组置尾操作的最小值
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。