大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
一 题目：旋转数组中的最小数字
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
这道题最直观的解法并不难，从头到尾遍历数组一次，我们就能找出最小的元素。这种思路的时间复杂度显然是O(n)。但是这个思路没有利用输入的旋转数组的特性，肯定达不到面试官的要求。
我们注意到旋转之后的数组实际上可以划分为两个排序的子数组，而且前面的子数组的元素都大于或者等于后面子数组的元素。我们还注意到最小的元素刚好是这两个子数组的分界线。在排序的数组中我们可以用二分查找法实现O(logn)的查找。
二 代码实现
#include "stdio.h" #include <iostream> using namespace std; #include <assert.h> // 遍历序列，找到最小值 int NormalFindMinVal(int *pStart, int *pEnd) { assert(pStart != NULL && pEnd != NULL); int min = *pStart++; while(pEnd - pStart >= 0) { if (min > *pStart) { min = *pStart; } pStart++; } return min; } int SearchMinInRotateaArr_1(int *pStart, int *pEnd) { if (pStart == NULL || pEnd == NULL) { return -1; } if (pEnd - pStart == 1) { return *pEnd; } int *pMid = NULL; pMid = pStart + (pEnd - pStart) / 2; if (*pMid >= *pStart && *pMid <= *pEnd) { return NormalFindMinVal(pStart, pEnd); } if (*pMid >= *pStart) { pStart = pMid; } else if(*pMid <= *pEnd) { pEnd = pMid; } return SearchMinInRotateaArr_1(pStart, pEnd); } // 找到旋转数组中的最小数字 int SearchMinInRotateaArr(int arr[], int nLen) { assert(arr != NULL && nLen > 0); int *pStart,*pEnd; pStart = arr; pEnd = pStart + nLen -1; return SearchMinInRotateaArr_1(pStart, pEnd); } int a[] = {3,4,5,1,2}; int b[] = {1,1,1,0,1,1}; int c[] = {1,2,3,4,5}; void main() { int data = SearchMinInRotateaArr(a,sizeof(a)/sizeof(a[0])); cout << data << endl; data = SearchMinInRotateaArr(b,sizeof(b)/sizeof(b[0])); cout << data << endl; data = SearchMinInRotateaArr(c,sizeof(c)/sizeof(c[0])); cout << data << endl; return; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/120169.html原文链接：https://javaforall.net
