赞
踩
Notice:
For problem 1-6, you should at least do the following things:
假设存在有序数组
a
s
c
e
n
d
i
n
g
A
r
r
a
y
=
{
x
1
,
x
2
⋯
x
k
,
x
k
+
1
⋯
x
n
}
ascendingArray = \{x_1,x_2\cdots x_k,x_{k+1}\cdots x_n\}
ascendingArray={x1,x2⋯xk,xk+1⋯xn},满足元素从小到大排序,按题意,假设选择数组元素
x
k
x_k
xk与
x
k
+
1
x_{k+1}
xk+1之间的点进行数组的旋转操作,得到数组
r
o
t
a
t
e
d
A
r
r
a
y
=
{
x
k
+
1
⋯
x
n
,
x
1
,
x
2
⋯
x
k
}
rotatedArray=\{x_{k+1}\cdots x_n,x_1,x_2\cdots x_k\}
rotatedArray={xk+1⋯xn,x1,x2⋯xk}. 可以看到,由于原数组是有序的,在旋转后得到的数组
r
o
r
a
t
e
d
A
r
r
a
y
roratedArray
roratedArray中依然满足部分有序,此时旋转点位于数组元素
x
n
x_n
xn与
x
1
x_1
x1之间,且两侧的元素分别满足:
x
k
+
1
,
x
k
+
2
⋯
,
x
n
≥
x
k
+
1
x
1
,
x
2
⋯
x
k
≤
x
k
+
1
x_{k+1},x_{k+2}\cdots,x_n\geq x_{k+1}\\ x_1,x_2\cdots x_k\leq x_{k+1}
xk+1,xk+2⋯,xn≥xk+1x1,x2⋯xk≤xk+1
而其他非旋转点的位置两侧的元素并不满足上述不等式关系:
问题要找出数组中的最小的元素,即找出旋转点位置即可,旋转点右边第一个元素即待求。由于算法的时间复杂度是 O ( n l o g n ) O(nlogn) O(nlogn),很容易想到用二分查找来做。
(1)对于旋转后的数组 r o t a t e d A r r a y rotatedArray rotatedArray,令 l o w low low指针初始指向下标为0的元素, h i g h high high指针初始指向下标为 n − 2 n-2 n−2的元素;
(2)当 l o w low low指针的值小于等于 h i g h high high指针的值,则执行第 ( 3 ) (3) (3)步;否则,执行第 ( 6 ) (6) (6)步;
(3)令
m
i
d
=
l
o
w
+
(
h
i
g
h
−
l
o
w
)
/
2
mid=low+(high-low)/2
mid=low+(high−low)/2,并判断数组元素
r
o
t
a
t
e
d
A
r
r
a
y
[
m
i
d
]
rotatedArray[mid]
rotatedArray[mid]与
r
o
t
a
t
e
d
A
r
r
a
y
[
m
i
d
+
1
]
rotatedArray[mid+1]
rotatedArray[mid+1]之间是否是旋转点,即是否满足如下关系:
r
o
t
a
t
e
d
A
r
r
a
y
[
m
i
d
]
≥
r
o
t
a
t
e
d
A
r
r
a
y
[
0
]
r
o
t
a
t
e
d
A
r
r
a
y
[
m
i
d
+
1
]
<
r
o
t
a
t
e
d
A
r
r
a
y
[
0
]
rotatedArray[mid]\geq rotatedArray[0]\\ rotatedArray[mid+1]<rotatedArray[0]
rotatedArray[mid]≥rotatedArray[0]rotatedArray[mid+1]<rotatedArray[0]
如果满足,算法结束,最小值即为
r
o
t
a
t
e
d
A
r
r
a
y
[
m
i
d
+
1
]
rotatedArray[mid+1]
rotatedArray[mid+1];
(4)如果数组元素满足:
r
o
t
a
t
e
d
A
r
r
a
y
[
m
i
d
]
≥
r
o
t
a
t
e
d
A
r
r
a
y
[
0
]
r
o
t
a
t
e
d
A
r
r
a
y
[
m
i
d
+
1
]
≥
r
o
t
a
t
e
d
A
r
r
a
y
[
0
]
rotatedArray[mid]\geq rotatedArray[0]\\ rotatedArray[mid+1]\geq rotatedArray[0]
rotatedArray[mid]≥rotatedArray[0]rotatedArray[mid+1]≥rotatedArray[0]
则
l
o
w
=
m
i
d
+
1
low=mid+1
low=mid+1, 接着执行第
(
2
)
(2)
(2)步;
(5)如果数组元素满足:
r
o
t
a
t
e
d
A
r
r
a
y
[
m
i
d
]
<
r
o
t
a
t
e
d
A
r
r
a
y
[
0
]
r
o
t
a
t
e
d
A
r
r
a
y
[
m
i
d
+
1
]
<
r
o
t
a
t
e
d
A
r
r
a
y
[
0
]
rotatedArray[mid]<rotatedArray[0]\\ rotatedArray[mid+1]<rotatedArray[0]
rotatedArray[mid]<rotatedArray[0]rotatedArray[mid+1]<rotatedArray[0]
则
h
i
g
h
=
m
i
d
−
1
high=mid-1
high=mid−1,接着执行第
(
2
)
(2)
(2)步;
(6)查找旋转点失败,程序返回,返回 r o t a t e d A r r a y [ 0 ] rotatedArray[0] rotatedArray[0]即为最小值;
binary_search(rotatedArray[0...n-1])
return binary_search_aux(rotatedArray,0,n-2)
binary_seatch_aux(rotatedArray,low,high)
while low <= high
Let mid = low + (high - low) / 2
if rotatedArray[mid] >= rotatedArray[0] && rotatedArray[mid+1] < rotaedArray[0]
return rotaedArray[mid+1]
else if rotatedArray[mid] >= rotatedArray[0] && rotatedArray[mid+1] >= rotatedArray[0]
low = mid + 1
else
high = mid - 1
return rotatedArray[0]
以旋转后得到的数组
[
6
,
7
,
1
,
2
,
3
,
4
,
5
]
[6,7,1,2,3,4,5]
[6,7,1,2,3,4,5]为例,在旋转点位置的查找过程中,子问题的规模能够指数级的降低。
令
T
(
n
)
T(n)
T(n)表示查找包含
n
n
n个元素的旋转后的数组的最小值所需要的时间,因为采取二分策略,问题的规模减半,且每次比较是有限几个数组元素之间的比较,所花费的时间为常数时间,因此我们得到如下递归表达式:
T
(
n
)
=
T
(
n
2
)
+
c
T(n) = T(\frac{n}{2})+c
T(n)=T(2n)+c
由此得到上述算法的时间复杂度为
O
(
l
o
g
n
)
O(logn)
O(logn),上述递归式易通过展开求解.
问题是要求二叉树中节点之间的最大距离,对于二叉树最常见的分治套路就是递归地求根节点的左右子树,那么问题就变成了递归地求根节点左右子树的最大距离,此时还需要考虑两节点的最大距离路径经过根节点的情况,问题的解就是左子树的最大距离、右子树的最大距离以及经过根节点的最大距离三者中的最大值。经过根节点的最大距离即为左右子树深度之和。
(0)输入:二叉树的根节点 T T T;输出:二叉树中节点的最大距离 m a x D i s t a n c e maxDistance maxDistance;
(1)如果二叉树根节点 T T T, 左右子树均为空,则返回最大距离 m a x D i s t a n c e = 0 maxDistance=0 maxDistance=0,当前调用结束;否则,顺序执行下一步;
(2)如果二叉树根节点
T
T
T,存在左子树,即T->left != NULL
,递归调用本身求左子树T->left
中节点的最大距离
d
i
s
t
a
n
c
e
1
distance1
distance1;否则,即左子树为空,
d
i
s
t
a
n
c
e
1
=
0
distance1=0
distance1=0;
(3)如果二叉树根节点
T
T
T,存在右子树,即T->right != NULL
,递归调用算法本身求右子树中节点的最大距离
d
i
s
t
a
n
c
e
2
distance2
distance2;否则,右子树为空,
d
i
s
t
a
n
c
e
2
=
0
distance2 = 0
distance2=0;
(4)求二叉树中两节点的最大距离经过根节点 T T T的情形下的最大距离 d i s t a n c e 3 distance3 distance3,其值即为根节点 T T T的左右子树的层数之和, d i s t a n c e 3 = l e v e l ( T → l e f t ) + l e v e l ( T → r i g h t ) distance3 = level(T\rightarrow left)+level(T\rightarrow right) distance3=level(T→left)+level(T→right);其中,左右子树的层数可以通过二叉树的层序遍历(通过队列来实现)得到。
(5)返回根节点为
T
T
T的二叉树中节点间的最大距离
m
a
x
D
i
s
t
a
n
c
e
maxDistance
maxDistance,当前调用结束。其中,
m
a
x
D
i
s
t
a
n
c
e
=
m
a
x
{
d
i
s
t
a
n
c
e
1
,
d
i
s
t
a
n
c
e
2
,
d
i
s
t
a
n
c
e
3
}
maxDistance = max\{distance1, distance2, distance3\}\\
maxDistance=max{distance1,distance2,distance3}
FIND-MAX-DISTANCE(T) //T is the root of the tree if T->left == NULL && T->right == NULL return 0 if T->left != NULL distance1 = FIND-MAX-DISTANCE(T->left) else distance1 = 0 if T->right != NULL distance2 = FIND-MAX-DISTANCE(T->right) else distance2 = 0 distance3 = LEVEL_TRAVERSE(T->left) + LEVEL_TRAVERSE(T->right) return max{distance1, distance2, distance3} LEVEL_TRAVERSE(T) //travel the tree from left to right, top to bottom if T == NULL return 0 Let depth = 0 queue<T> q q.push(T) while q is not empty Let n = q.size() depth++ for i=1 to i=n T front = q.front() q.pop() if front->left != NULL q.push(front->left) if front->right != NULL q.push(front->right) return depth
以上图为例,可以看到求二叉树节点间的最大距离归结成了求二叉树的左右子树中节点间的最大距离以及左右子树的层数问题,对于左右子树节点数大致相等的情况,问题规模能够指数级下降。
论述一:由于算法是通过递归调用本身来实现的,递归存在边界,即到叶子节点或者空节点时返回,因而算法能够停止;
论述二:二叉树 T T T中的距离最大的两个节点有三种情况,
此三种情况在算法中都得到了考虑;
论述三:
f
i
n
d
M
a
x
D
i
s
t
a
n
c
e
(
T
)
=
m
a
x
{
f
i
n
d
M
a
x
D
i
s
t
a
n
c
e
(
T
→
l
e
f
t
)
,
f
i
n
d
M
a
x
D
i
s
t
a
n
c
e
(
T
→
r
i
g
h
t
)
,
d
e
p
t
h
(
T
→
l
e
f
t
)
+
d
e
p
t
h
(
T
→
r
i
g
h
t
)
}
findMaxDistance(T) = max\{findMaxDistance(T\rightarrow left),findMaxDistance(T\rightarrow right), depth(T\rightarrow left)+depth(T\rightarrow right)\}
findMaxDistance(T)=max{findMaxDistance(T→left),findMaxDistance(T→right),depth(T→left)+depth(T→right)}
令
T
(
n
)
T(n)
T(n)表示求包含
n
n
n个节点的二叉树中两个节点的最大距离所需要的时间,为了分析的方便,假定二叉树的左子树节点数目为
α
∗
n
\alpha\ast n
α∗n,二叉树的右子树节点数目为
β
∗
n
\beta\ast n
β∗n,则递归调用求左子树最大距离的时间为
T
(
α
∗
n
)
T(\alpha\ast n)
T(α∗n),求右子树最大距离的时间为
T
(
β
∗
n
)
T(\beta\ast n)
T(β∗n),求经过根节点的最大距离是通过对左右子树进行层序遍历求得到的深度相加得来的,层序遍历的时间复杂度为
O
(
n
)
O(n)
O(n),因而时间复杂度的递归表达式为:
T
(
n
)
=
T
(
α
∗
n
)
+
T
(
β
∗
n
)
+
O
(
n
)
α
+
β
=
1
T(n) = T(\alpha\ast n)+T(\beta\ast n)+O(n)\\ \alpha + \beta = 1
T(n)=T(α∗n)+T(β∗n)+O(n)α+β=1
将上述递归表达式通过递归树展开,每一层都为
c
n
cn
cn,共有
l
o
g
n
logn
logn层,因此总的时间复杂度为
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn).
题目要求完全二叉树中的局部最小值,并且题目要求仅通过 O ( l o g n ) O(logn) O(logn)次探测,根据这一特征,很容易看出该过程与数组的二分查找过程类似。完全二叉树中节点的值均不相同。
FIND-LOCAL-MIN(T) //T is the root of tree
if T->left == NULL && T->right == NULL // T is a left of the tree
return T
Let T and R be T's children
Let X_T be T's root value
Let X_L be T's left children's root value
Let X_R be T's right children's root value
if X_L < X_T
return FIND-LOCAL-MIN(L)
else if X_R < X_T
return FIND-LOCAL-MIN(R)
else
return X_T
以上图为例,在完全二叉树中递归地求解子问题,使得每次问题的规模变为原来的一半,当到达递归的边界(叶子节点)或者子树的根节点值小于其孩子节点的值时,递归返回,得到局部最小值。
令
T
(
n
)
T(n)
T(n)表示包含n个节点的完全二叉树查找其局部最小值的时间,显然,每次递归调用能够将问题的规模减为原来的一半,并且只需要对一个子树进行递归即可,中间比较的时间为常数时间。因此得到下列递归表达式:
T
(
n
)
=
T
(
n
2
)
+
c
(1)
T(n) = T(\frac{n}{2}) + c\tag{1}
T(n)=T(2n)+c(1)
因此算法的时间复杂度为
O
(
l
o
g
n
)
O(logn)
O(logn).
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。