C语言输出旋转后数组中的最小数元素的算法原理与实例
2019/7/10 23:00:20
本文主要是介绍C语言输出旋转后数组中的最小数元素的算法原理与实例,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
问题描述:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个排好序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为1。
思路:这道题最直观的解法并不难。从头到尾遍历数组一次,就能找出最小的元素,时间复杂度显然是O(n)。但这个思路没有利用输入数组的特性。既然有时间复杂度更小的算法,我们容易想到二分查找,因为它的时间复杂度为O(logn)。这个问题是否可以运用二分查找呢?答案是肯定的。观察一下数组的特性,首先递增(称为递增a),然后突然下降到最小值,然后再递增(称为递增b)。当然还有一种特殊情况,就是数组递增,中间没有下降,即旋转元素个数为0。
对于一般的情况,假设A为输入数组,left 和 right 为数组左右边界的坐标,考察中间位置的值A[mid] ,如果A[mid] <= A[right],表明处于递增b,调整右边界 right = mid;如果A[mid] >= A[left],表明处于递增a,因此调整左边界left = mid。当左右边界相邻时,较小的一个就是数组的最小值。其实,对于一般情况,右边界所指的元素为最小值。
对于特殊情况,即旋转个数为0。按照上述算法,右边界会不断减少,直到与左边界相邻。这时左边界所指的元素为最小值。下面给出几组测试案例:
//{1,2,3,4,5,6,7,8,9,10} 1 //{4,5,6,7,8,9,10,1,2,3} 1 //{1,1,1,1,1,1,1,1,1,1} 1 //{1,9,10,1,1,1,1,1,1,1} 1 //{9,9,9,9,9,9,9,10,1,9} 9 错误
第五组的结果是错误的。其实,上述算法适用于严格递增的数组,对于非严格递增,用二分法无法保证正确解。有兴趣的读者,可以试试,对于非严格递增的序列,是否可以用二分法得到正确解。
参考代码:
//函数功能 : 旋转数组的最小元素 //函数参数 : pArray指向数组,len为数组长度 //返回值 : 最小元素 int FindMin(int *pArray, int len) { if(pArray == NULL || len <= 0) return 0; int left = 0, right = len - 1, mid; while(right - left != 1) { mid = left + ((right - left)>>1); if(pArray[right] >= pArray[mid]) right = mid; else if(pArray[left] <= pArray[mid]) left = mid; } return pArray[right] > pArray[left] ? pArray[left]: pArray[right]; }
这篇关于C语言输出旋转后数组中的最小数元素的算法原理与实例的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-25Elevate Your Lead Generation Game with Maps Scraper AI
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能