【C/C++练习题】旋转数组的最小数字

举报
王建峰 发表于 2021/11/19 00:11:30 2021/11/19
【摘要】 《剑指offer》面试题11   题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为1。   算法基本思想(二分查找):数组划分成两...

《剑指offer》面试题11

 

题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为1。

 

算法基本思想(二分查找):数组划分成两个子数组且前面的子数组中元素的数值都大于等于后面数组中的数值,根据旋转数组的特点,选取中间元素mid,判断目标元素在mid的左边还是右边,缩小待查找区间范围。以相同的规则进行二次查找... 直到区间中有两个元素,选取右边的元素为最小值返回。

 

代码分析

码云:https://gitee.com/hinzer/sword_to_offer/blob/master/questions/question_11.cpp


  
  1. #include "iostream"
  2. using namespace std;
  3. int forMin(int* numbers, int length);
  4. //旋转数组的最小数字(二分法)
  5. //输入:数组首地址numbers 数组长度length
  6. //返回:最小值
  7. int Min(int* numbers, int length)
  8. {
  9. //1、检查参数有效性
  10. if (numbers == nullptr || length <= 0)
  11. {
  12. // throw new std::exception("Invalid paramenters");
  13. return -1;
  14. }
  15. int index1 = 0;
  16. int index2 = length-1;
  17. int mid = index1; //3、考虑特殊情况(第二个子数组为空,数组为升序排列)
  18. //2、二分查找
  19. while (numbers[index1] >= numbers[index2])
  20. {
  21. if (index2 - index1 == 1)
  22. {//区间缩小到两个元素
  23. return numbers[index2];
  24. }
  25. //二分区间
  26. mid = (index1 + index2)/2;
  27. //4、考虑第二种特殊情况(mid index1 index2对应的值相等)
  28. if ((numbers[index1] == numbers[index2]) && (numbers[mid] == numbers[index1]))
  29. {//直接轮询一遍,找出最小的元素
  30. return forMin(numbers, length);
  31. }
  32. if (numbers[mid] >= numbers[index2])
  33. {//中间值大于最右元素
  34. index1 = mid;
  35. }
  36. if (numbers[mid] <= numbers[index2])
  37. {//中间值小于最右元素
  38. index2 = mid;
  39. }
  40. }
  41. return numbers[mid];
  42. }
  43. //遍历数组,找出最小值
  44. //输入:数组首地址numbers 数组长度length
  45. //返回:最小值
  46. int forMin(int* numbers, int length)
  47. {
  48. int res = numbers[0];
  49. for (int i = 1; i < length; i++)
  50. {
  51. if (numbers[i] < res)
  52. {
  53. res = numbers[i];
  54. }
  55. }
  56. return res;
  57. }
  58. //测试1
  59. void test01()
  60. {
  61. int numbers[5] = {3, 4, 5, 1, 2}; //普通旋转数组
  62. int numbers1[5] = {1, 2, 3, 4, 5}; //特殊旋转数组1
  63. int res = Min(numbers, sizeof(numbers)/sizeof(int));
  64. cout << "普通旋转数组:" << res << endl;
  65. int res1 = Min(numbers1, sizeof(numbers1)/sizeof(int));
  66. cout << "特殊旋转数组一:" << res1 << endl;
  67. }
  68. //测试2
  69. void test02()
  70. {
  71. int numbers[5] = {1, 0, 1, 1, 1}; //特殊情况
  72. int res = Min(numbers, sizeof(numbers)/sizeof(int));
  73. cout << "特殊旋转数组二:" << res << endl;
  74. }
  75. int main(int argc, char const *argv[])
  76. {
  77. test01();
  78. test02();
  79. return 0;
  80. }

 

 

运行

 

 

 

文章来源: blog.csdn.net,作者:hinzer,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/feit2417/article/details/98211936

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200