我的刷题日记（3）

我会带着你远行 2021-11-16 06:20 202阅读 0赞

2019年8月2日

## 旋转数组的最小数字  ##

## 题目描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素，例如数组\{3,4,5,1,2\}为\{1,2,3,4,5\}的一个旋转，该数组的最小值为1。NOTE：给出所有元素都大于0，若数组大小为0，请返回0。 ##

***时间限制：3秒  
空间限制：32768K***

首先要弄清楚什么是**非减排序数组**：  
举例：  
1，2，3，4…这是递增排列  
5，4，3，2，1…这是递减排列  
1，2，2，3，4，4，5，6，7，7…这是非递减排列  
9，8，8，7，6，5，5，… 这是非递增排列

我的理解就是：数组内的元素从第二项开始，每一项都大于等于该项的前一项  
即F(n) >= F(n-1) n>1

（有关算法实现请移步[我的常用算法实现][Link 1]）  
直接上代码

方法：二分法

运行时间：135ms  
占用内存：9996k

function minNumberInRotateArray(arr){
    	let len = arr.length;
    	if(len == 0){
    		return 0
    	}
    	let start = 0;
    	let end = len -1;
    	while(start < end){
    		let middle = Math.floor((start + end)/2);
    		if(arr[middle] > arr[end]){  // 说明middle右边是旋转过去的
    			start = middle +1;   
    		}else if(arr[middle] == arr[end]){  //数组成员重复
    			end = end -1
    		}else{
    			end = middle;
    		}
    	}
    	return arr[start]      //  非减排序数组，第一个是最小的
    }

[Link 1]: https://blog.csdn.net/weixin_43572937/article/details/88430264

发表评论取消回复

表情：

评论列表（有 0 条评论，202人围观）

还没有评论，来说两句吧...

相关阅读

相关刷题日记08《BFS》

概念 > 宽度优先[搜索算法][Link 1]（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra[单源最短路径][Li

电玩女神/ 2024年03月17日 21:40/ 0 赞/ 37 阅读

相关我的刷题日记（25）

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。 var findMedianSortedArr

系统管理员/ 2022年12月24日 09:52/ 0 赞/ 102 阅读

相关我的刷题日记（24）

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。 var lengthOfLongestSubstring = function(s) {

Bertha 。/ 2022年12月24日 04:55/ 0 赞/ 15 阅读

相关我的刷题日记（23）

给出两个非空的数组用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个位置只能存储一位数字。如果，我们将这两个数相加起来，则会返回

Myth丶恋晨/ 2022年12月24日 03:54/ 0 赞/ 116 阅读

相关我的刷题日记（22）

两数之和给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案

女爷i/ 2022年12月23日 09:37/ 0 赞/ 85 阅读

相关 Leetcode | 刷题日记(1)

本文记录个人刷题记录推荐两个刷题网站：地址：https://leetcode.com/ 另外一个地址：http://www.lintcode.com/ 1.Wr

深藏阁楼爱情的钟/ 2022年07月18日 01:52/ 0 赞/ 107 阅读

相关我的刷题日记（1）

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中

短命女/ 2022年03月11日 12:20/ 0 赞/ 115 阅读

相关我的刷题日记（2）

2019年7月29日斐波那契数列题目描述：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0） n<=39

以你之姓@/ 2021年11月17日 00:40/ 0 赞/ 215 阅读

相关我的刷题日记（3）

2019年8月2日旋转数组的最小数字题目描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的

我会带着你远行/ 2021年11月16日 06:20/ 0 赞/ 203 阅读

相关我的刷题日记（4）

2018年8月3日矩形覆盖标题我们可以用21的小矩形横着或竖着去覆盖一个更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2\n的大矩形，总共有多少种方法？

妖狐艹你老母/ 2021年11月11日 01:04/ 0 赞/ 170 阅读