如何解决C++中查找与排序的面试题-创新互联
这篇文章将为大家详细讲解有关如何解决C++中查找与排序的面试题，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。
题目：
旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，输入一个递增排序的数组的一个旋转，输出旋转数字的最小元素。
例：{2,3,4,0,1}是{0,1,2,3,4}的旋转，该数组最小值为0
程序1.0
失败的程序，从头遍历一遍，时间复杂度O（N），这个思路没有利用输入旋转数组的特性，随便实现了但是却是失败的
int MinNum(int* array, int length)
{
int cur = array[0];
for (int i = 1; i < length; i++)
{
if (array[i]程序2.0
方法类似于二分查找
int MinNum(int* array, int length)
{
assert(array);
assert(length>0);
int left = 0;
int right = length - 1;
int mid = left;//初始化为0，这样若旋转了0个元素则直接返回
while (array[left] >= array[right])//数组为旋转后数组
{
if (right - left == 1)
{
mid = right;
break;
}
mid = (left + right) / 2;
if (array[mid] >= array[left])
{
left = mid;
}
else if (array[mid] <= array[right])
{
right = mid;
}
}
return array[mid];
}
//在第一次检测时发现怎么跑都是返回的第一个元素的值，后来检测时发现是在while循环块中在定义mid时在前面不小心加了个int，这使得这个mid为这个块的局部变量，出了这个循环后就被丢弃程序3.0
在2.0中有考虑不完善的地方，若数组为{1,0,1,1,1}或者为{1,1,1,0,1}，其左右和中间都是1，无法移动两个指针来缩小查找范围，因而不得不采取顺序查找的方法
int MinInOrder(int *array,int left,int right)
{
int ret = array[left];
for (int i = left + 1; i <= right; i++)
{
if (ret>array[i])
{
ret = array[i];
}
}
return ret;
}
int MinNum(int* array, int length)
{
assert(array);
assert(length > 0);
int left = 0;
int right = length - 1;
int mid = left;
while (array[left] >= array[right])
{
if (right - left == 1)
{
mid = right;
break;
}
mid = (left + right) / 2;
if (array[left] == array[right] && array[left] == array[mid])
{
return MinInOrder(array, left, right);
}
if (array[mid] >= array[left])
{
left = mid;
}
else if (array[mid] <= array[right])
{
right = mid;
}
}
return array[mid];
}测试
void test()
{
int a[10] = { 8,9,10,11,1,2,3,4,5,6 };
cout<关于“如何解决C++中查找与排序的面试题”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
名称栏目：如何解决C++中查找与排序的面试题-创新互联
分享URL：http://pwwzsj.com/article/dddjsg.html
