题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,则该旋转数组的最小值为1.
代码:(版本1.0 这个程序还没有分析到位)
//这里的做法类似于二分查找,设置两个索引start ,end,分别指向数组首元素和末尾的元素,设置索引mid=(start+end)/2,比较索引end指向的元素和mid索引指向的元素的大小,并缩小查找范围,直到start==end,最后 return end;
注意:如果开始 是就有A[start]<=A[end],由于该数组并没有旋转,A[0]即为最小值,不用在进行二分查找,那么直接返回A[0]即可。
#include<iostream>
using namespace std;
#define MAX 10
int minvalue(int *numbers,int length)
{
int start=0;
int end=length-1;
if(numbers==NULL || length<=0)
{
cout<<"error :array is empty!"<<endl;
return 0;
}
if(numbers[start]<=numbers[end])
end=start;
else
{
int mid;
while(start<end)
{
mid=(start+end)/2;
if(numbers[mid]<=numbers[end])
{
end=mid;
}
else if(numbers[mid]>numbers[end])
{
start=mid+1;
}
}
}
return end;
}
int main(void)
{
int *numbers=(int *)malloc(sizeof(int)*MAX);
int length;
int i;
cout<<"input actual length of the array:"<<endl;
cin>>length;
cout<<"input the array:"<<endl;
for(i=0;i<length;i++)
{
cin>>numbers[i];
}
cout<<"the minimum element of the array is:"<<numbers[minvalue(numbers,length)]<<endl;
return 0;
}
上述代码在三个索引指向的值都相同时,输出错误,因为此时无法再用类二分查找的方法缩小查找范围,只能使用暴力查找
代码2(完善后)
#include<iostream>
using namespace std;
#define MAX 10
int minvalue(int *numbers,int length)
{
int start=0;
int end=length-1;
int mid=(start+end)/2;
if(numbers==NULL || length<=0)
{
cout<<"error :array is empty!"<<endl;
return 0;
}
//若开始时,说明原数组并未进行旋转,
//numbers[start]就小于numbers[end],索引start指向的元素即为最小值
if(numbers[start]<numbers[end])
end=start;
//若三个索引指向的元素都相等,用类二分查找的
//的方法不能解决问题,只能使用暴力查找。
else if(numbers[start]==numbers[mid] && numbers[start]==numbers[end])
{
//cout<<"enter the else if"<<endl;
//end=numbers[0];
end=0;
for(int i=0;i<length;i++)
{
if(end>=numbers[i])
end=i;
}
}
else
{//循环在索引start==end 时停止,此时两个索引均指向数组中最小值对应的位置。
while(start<end)
{
mid=(start+end)/2;
if(numbers[mid]<=numbers[end])
{
end=mid;
}
else if(numbers[mid]>numbers[end])
{
start=mid+1;
}
}
}
return end;
}
int main(void)
{
int *numbers=(int *)malloc(sizeof(int)*MAX);
int length;
int i;
cout<<"input actual length of the array:"<<endl;
cin>>length;
cout<<"input the array:"<<endl;
for(i=0;i<length;i++)
{
cin>>numbers[i];
}
cout<<"the minimum element of the array is:"<<numbers[minvalue(numbers,length)]<<endl;
return 0;
}
源码3(剑指offer书上源码)
// MinNumberInRotatedArray.cpp : Defines the entry point for the console application.
//
// 《剑指Offer——名企面试官精讲典型编程题》代码
// 著作权所有者:何海涛
#include "stdafx.h"
#include<exception>
int MinInOrder(int* numbers, int index1, int index2);
int Min(int* numbers, int length)
{
if(numbers == NULL || length <= 0)
throw new std::exception("Invalid parameters");
int index1 = 0;
int index2 = length - 1;
int indexMid = index1;
while(numbers[index1] >= numbers[index2])
{
// 如果index1和index2指向相邻的两个数,
// 则index1指向第一个递增子数组的最后一个数字,
// index2指向第二个子数组的第一个数字,也就是数组中的最小数字
if(index2 - index1 == 1)
{
indexMid = index2;
break;
}
// 如果下标为index1、index2和indexMid指向的三个数字相等,
// 则只能顺序查找
indexMid = (index1 + index2) / 2;
if(numbers[index1] == numbers[index2] && numbers[indexMid] == numbers[index1])
return MinInOrder(numbers, index1, index2);
// 缩小查找范围
if(numbers[indexMid] >= numbers[index1])
index1 = indexMid;
else if(numbers[indexMid] <= numbers[index2])
index2 = indexMid;
}
return numbers[indexMid];
}
int MinInOrder(int* numbers, int index1, int index2)
{
int result = numbers[index1];
for(int i = index1 + 1; i <= index2; ++i)
{
if(result > numbers[i])
result = numbers[i];
}
return result;
}
// ====================测试代码====================
void Test(int* numbers, int length, int expected)
{
int result = 0;
try
{
result = Min(numbers, length);
for(int i = 0; i < length; ++i)
printf("%d ", numbers[i]);
if(result == expected)
printf("\tpassed\n");
else
printf("\tfailed\n");
}
catch (...)
{
if(numbers == NULL)
printf("Test passed.\n");
else
printf("Test failed.\n");
}
}
int _tmain(int argc, _TCHAR* argv[])
{
// 典型输入,单调升序的数组的一个旋转
int array1[] = {3, 4, 5, 1, 2};
Test(array1, sizeof(array1) / sizeof(int), 1);
// 有重复数字,并且重复的数字刚好的最小的数字
int array2[] = {3, 4, 5, 1, 1, 2};
Test(array2, sizeof(array2) / sizeof(int), 1);
// 有重复数字,但重复的数字不是第一个数字和最后一个数字
int array3[] = {3, 4, 5, 1, 2, 2};
Test(array3, sizeof(array3) / sizeof(int), 1);
// 有重复的数字,并且重复的数字刚好是第一个数字和最后一个数字
int array4[] = {1, 0, 1, 1, 1};
Test(array4, sizeof(array4) / sizeof(int), 0);
// 单调升序数组,旋转0个元素,也就是单调升序数组本身
int array5[] = {1, 2, 3, 4, 5};
Test(array5, sizeof(array5) / sizeof(int), 1);
// 数组中只有一个数字
int array6[] = {2};
Test(array6, sizeof(array6) / sizeof(int), 2);
// 输入NULL
Test(NULL, 0, 0);
return 0;
}
分享到:
相关推荐
面试题 6:旋转数组的最小数字(考点:查找和排序) 6 面试题 7:斐波那契数列(考点: 递归和循环) 7 面试题 8:跳台阶(考点: 递归和循环) 7 面试题 9:变态跳台阶(考点: 递归和循环) 8 面试题 10:矩形覆盖(考点...
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 解题思路参考博客
剑指offer面试题精选 剑指offer部分面试题使用javascript实现,配合grunt,使用karma和jasmine完成自动测试,使用jshint做代码检测。 面试题 面试题03:二维数组中的查找 面试题06:重建二叉树 面试题08:旋转数组中...
面试题11:旋转数组的最小数字 +2 二分查找 面试题12:矩阵中的路径 +2 DFS 面试题13:机器人的运动范围 +2 DFS+BFS 面试题14 - I:剪绳子 +2 动态规划 面试题14 - II:剪绳子 +2 动态规划 面试题15:二进制中1的...
面试题8 旋转数组的最小数字 面试题9 斐波那契数列 面试题10 二进制中1的个数 第3章 高质量代码 3.3 代码的完整性 面试题11 数值的整数次方 面试题12 打印1到最大的n位数 面试题13 O(1)时间删除链表结点 面试题14 ...
leetcode 剑指 Offer 50 道经典算法题视频讲解 「剑指 Offer」是何海涛写的一本算法面试书,书中...旋转数组的最小数字 - - leetcode 153 | lintcode 159 斐波那契数列 - - leetcode 509 | lintcode 366 二进制中 1 的
剑指Offer编程题目录 二维数组中的查找: 替换空格: 从尾到头打印链表: 重建二叉树: 用两个栈来实现队列: 旋转数组的最小数字: 斐波那契数列: 跳台阶: 跳台阶2: 矩形覆盖: 二进制中1的个数 数值的整数次方: 调整数组...
旋转数组的最小数字 面试题12 矩阵中的路径 面试题13 机器人的运动范围 面试题14- I 剪绳子 面试题14- II 剪绳子 面试题15 二进制中1的个数 面试题16 数值的整数次方 面试题17 打印从1到最大的n位数 面试题18 删除...
11 旋转数组的最小数字 12 矩阵中的路径 13 机器人的运动范围 14 剪绳子 15 二进制中1的个数 第3章 高质量的代码 3.3 代码的完整性 16 数值的整数次方 17 打印从1到最大的n位数 18 删除链表中的节点 19 正则表达式 ...
leetcode中文版 剑指Offer的Python解答 剑指Offer的Python解答,不断更新。如果数学公式无法正确显示,可以clone到本地查看...旋转数组的最小数字 二分法 矩阵中的路径 dfs 机器人的运动范围 dfs,bfs 剪绳子 数学,动
每日刷题计划,记录做过的题目,内容包含剑指offer、程序员面试金典(CTCI)、数据结构 下面标题括号内的为对应包名 剑指offer(offer) java实现 03二维数组中的查找 04替换空格 05从尾到头打印链表 06重建二叉树 07用...
leetcode双人赛 ...旋转数组 数组中的第K个最大元素 滑动窗口最大值 移动零 前 K 个高频元素 两个数组的交集 两个数组的交集 II 翻转对 数组的相对排序 剑指 Offer 40. 最小的k个数 面试题 08.03. 魔术索引