博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
数组-Find Minimum in Rotated Sorted Array
阅读量:5169 次
发布时间:2019-06-13

本文共 458 字,大约阅读时间需要 1 分钟。

排序数组在旋转后,可以分为前后两个排序子序列。在没有相同元素的情况下,前一个数组中的元素均大于后一个数组中的元素。

如果我们要找最小元素,则只要找到两个数组的分界点即可,即第二个子序列的开始元素。

由于子序列分别有序,所以我们可以采用二分查找的思想来解决问题,不断缩小查询范围。

这道题要注意特例情况:

1.数组中只有一个元素

2.把排序数组前面的0个元素搬到最后面,即排序数组本身,这仍然是一个数组的旋转

3.如果数组中含有相同的元素,则情况更为复杂。此时用二分查找不太合适,要考虑使用顺序查找。

int findMin(vector
& nums) { int l=0,r=nums.size()-1; if(nums.size()==0) return -1; if(nums[l]

 

转载于:https://www.cnblogs.com/summerkiki/p/5476817.html

你可能感兴趣的文章
setImageBitmap和setImageResource
查看>>
springMVC4 注解配置实例
查看>>
单片机编程
查看>>
Filter in Servlet
查看>>
Linux--SquashFS
查看>>
Application Pool Identities
查看>>
2017-3-24 开通博客园
查看>>
【MySQL性能优化】MySQL常见SQL错误用法
查看>>
Vue2全家桶之一:vue-cli(vue脚手架)超详细教程
查看>>
Struts 2 常用技术
查看>>
树形DP
查看>>
python flask解决上传下载的问题
查看>>
语法测试
查看>>
CES1
查看>>
CES2
查看>>
文件方式实现完整的英文词频统计实例
查看>>
ListControl的用法
查看>>
单个SWF文件loading加载详解(转)
查看>>
SQLServer中的CTE通用表表达式
查看>>
linux第1天 fork exec 守护进程
查看>>