个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
26
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章求解旋转数组的最小数字由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
求解旋转数组的最小数字 。
题目描述:
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小数组。例如数组{3,4,5,1,2}是数组{1,2,3,4,5}的旋转数组，该数组的最小值为1.
思路解析:
O(N)的算法 。
这种算法的思想就是遍历这个数组，由于这个数组是两部分有序的数组，因此遍历这个数组时当后一个数字小于前一个数字时，则后一个（即较小）一定为整个数组中最小的数字.
这种算法的思想很简单，但就是时间复杂度较大，因此不是很好的算法.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
int
minNumberInRotateArray(vector<
int
> rotateArray)
{
if
(rotateArray.empty())
return
-
1
;
unsigned
int
i=
0
;
for
(; i<rotateArray.size()-
1
; i++)
{
if
(rotateArray[i] > rotateArray[i+
1
])
break
;
}
return
rotateArray[i+
1
];
}
|
O(logN)的算法 。
这种算法思想类似于二分查找，首先每次找到数组中中间的数字mid，如果mid大于最左端left，说明最小数在mid的右侧区间，则改变left，置left为mid；如果mid小于数组右侧right，说明最小数在mid的左侧区间，则改变right为mid….当left的数字小于等于right的数字时，说明已经找到最小数，这个也是循环结束的条件 。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
int
minNumberInRotateArray(vector<
int
> rotateArray)
{
if
(rotateArray.empty())
return
-
1
;
unsigned
int
left=
0
;
unsigned
int
right=rotateArray.size()-
1
;
unsigned
int
mid=left;
while
(rotateArray[left] >= rotateArray[right])
{
if
(right-left ==
1
)
{
mid = right;
break
;
}
mid = left+((right-left)>>
1
);
if
(rotateArray[mid]==rotateArray[left] && rotateArray[right]==rotateArray[mid])
return
rotateArray[mid];
if
(rotateArray[mid] >= rotateArray[left])
left = mid;
else
if
(rotateArray[mid] <= rotateArray[right])
right = mid;
}
return
rotateArray[mid];
}
|
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！ 。
原文链接：http://blog.csdn.net/qq_33951180/article/details/72730144 。
最后此篇关于求解旋转数组的最小数字的文章就讲到这里了,如果你想了解更多关于求解旋转数组的最小数字的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
26
4
0
我正在使用混合效应模型，并且由于我的方法的特殊性我需要解决下面模型的积分，然后制作图表获得的估计值。 换句话说，我需要求解下面的积分: 其中，di^2 是我模型中的 Var3，dh 是混合效应模型对应
我有一个方程组，我想用数值方法求解它。给定起始种子，我想得到一个接近的解决方案。让我解释。 我有一个常量向量，X，值: X <- (c(1,-2,3,4)) 和一个向量 W 的权重: W <- (c(
假设我有以下方程组: a * b = 5 sqrt(a * b^2) = 10 如何求解 R 中 a 和 b 的这些方程？ 我想这个问题可以说是一个优化问题，具有以下功能......？ fn <- f
我在 R 中有一个简单的通量模型。它归结为两个微分方程，对模型中的两个状态变量进行建模，我们将它们称为 A和 B .它们被计算为四个分量通量的简单差分方程 flux1-flux4 , 5 个参数 p1
R有什么办法吗？求解给定单变量函数的反函数？动机是我以后告诉R使用值向量作为反函数的输入，以便它可以吐出反函数值。 例如，我有函数 y(x) = x^2 ，逆是 y = sqrt(x) .有没有办法R
我在字符串中有以下方程 y = 18774x + 82795 求解x我会这样做:- x = (y-82795) / 18774 我知道y的值 但是方程一直在变化，并且始终采用字符串格式 是否可以简单地
如果我用 diophantine(2*x+3*y-5*z-77) 我收到了这个结果。 {(t_0, -9*t_0 - 5*t_1 + 154, -5*t_0 - 3*t_1 + 77)} 到目前为止还
我正在尝试求解仅限于正解的 ODE，即: dx/dt=f(x) x>=0。 在 MATLAB 中这很容易实现。 R 是否有任何变通方法或包来将解决方案空间限制为仅正值？ 这对我来说非常重要，不幸的是没
下面的 ANTLR 文法中的 'expr' 规则显然是相互左递归的。作为一个 ANTLR 新手，我很难解决这个问题。我已经阅读了 ANTLR 引用书中的“解决非 LL(*) 冲突”，但我仍然没有看到解
我有一个关于在 R 中求解函数的可能性的非常基本的问题，但知道答案确实有助于更好地理解 R。 我有以下等式: 0=-100/(1+r)+(100-50)/(1+r)^2+(100-50)/(1+r)^
我正在编写使用递归回溯来解决 8 个皇后问题的代码(将 n 个国际象棋皇后放在 n × n 的棋盘上，这样皇后就不会互相攻击)。 我的任务是创建两个方法:编写一个公共(public)solveQuee
我不知道在以下情况下如何进行，因为最后一个方程没有所有 4 个变量。所以使用了等式下面的代码，但这是错误的......有谁知道如何进行？ 方程: 3a + 4b - 5c + d = 10 2a +
假设我们有这个递归关系，它出现在 AVL 树的分析中: F1 = 1 F2 = 2 Fn = Fn - 1 + Fn - 2 + 1(其中 n ≥ 3) 你将如何解决这个递归以获得 F(n) 的封闭形
在Maple中，有谁知道是否存在一个函数来求解变量？例如，我正在尝试求解 r 的 solve4r=(M-x^y)*(r^(-1)) mod (p-1)。所以我知道 M、x、y 和 p 的值，但不知道
我也问过这个here在声音设计论坛上，但问题是沉重的计算机科学/数学，所以它实际上可能属于这个论坛: 因此，通过读取文件中的二进制文件，我能够成功地找到关于 WAV 文件的所有信息，除了 big si
我有以下问题: 设 a 和 b 为 boolean 变量。是否可以设置 a 和 b 的值以使以下表达式的计算结果为 false？ b or (((not a) or (not a)) or (a or
我需要用 C 求解这个超越方程: x = 2.0 - 0.5sen(x) 我试过这个: double x, newx, delta; x = 2.0 - 0.5; newx = sin(x); del
我在 Windows 上使用 OpenCV 3.1。 一段代码: RNG rng; // random number generator cv::Mat rVec = (cv::Mat_(3, 1)
我正在尝试求解一个包含 3 个变量和数量可变的方程的方程组。 基本上，系统的长度在 5 到 12 个方程之间，无论有多少个方程，我都试图求解 3 个变量。 看起来像这样: (x-A)**2 + (y-
我正在尝试为有限差分法设计一种算法，但我有点困惑。所讨论的 ODE 是 y''-5y'+10y = 10x，其中 y(0)=0 且 y(1)=100。所以我需要一种方法来以某种方式获得将从关系中乘以“
我是一名优秀的程序员,十分优秀！