A*******e
发帖数: 2419 | 1 思路不难，但写起来怎么还有点麻烦？比如如何简洁地处理某个数组只有一个元素？
LC上贴出的答案可读性都不太好啊。 | l******s
发帖数: 3045 | | w**z
发帖数: 8232 | 3 leetcode 出的书上有些答案确实很难读懂。过于追求编程技巧，以至于程序难读。
【在 A*******e 的大作中提到】
: 思路不难，但写起来怎么还有点麻烦？比如如何简洁地处理某个数组只有一个元素？
: LC上贴出的答案可读性都不太好啊。
| s**x
发帖数: 7506 | | A*******e
发帖数: 2419 | 5 第四题。
【在 l******s 的大作中提到】
: Leetcode number？
| A*******e
发帖数: 2419 | 6 好像是算法导论的习题。不知标准答案是啥。
【在 s**x 的大作中提到】
: 我一直认为这是最难的一道。
| d****n
发帖数: 397 | 7 贴一个python 代码。 这个有点像quick sort里面的deterministic nlgn 算法。重点
是将rank r按两个数组长度分配。
然后在舍弃两个数组其中一个的左边一段。
class Solution:
# @return a float
def findMedianSortedArrays(self, A, B):
m = len(A)
n = len(B)
i = 0
j = m - 1
s = 0
t = n - 1
if (m + n) % 2 == 0:
r1 = (m + n) / 2
r2 = r1 + 1
median = (self.findRankr(A, B, i, j, s, t, r1) + self.findRankr(
A, B, i, j, s, t, r2)) / 2.0
else:
r1 = (m + n) / 2 + 1
median = self.findRankr(A, B, i, j, s, t, r1) / 1.0
return median
def findRankr(self, A, B, i, j, s, t, r):
if i == j + 1:
return B[s + r - 1]
elif s == t + 1:
return A[i + r - 1]
else:
if r == 1:
return min(A[i], B[s])
m = j - i + 1
n = t - s + 1
k = r * m / (m + n)
if k == 0:
k += 1
l = r - k
if A[i + k - 1] == B[s + l - 1]:
return A[i + k - 1]
elif A[i + k - 1] < B[s + l - 1]:
return self.findRankr(A, B, i + k, j, s, t, r - k)
else:
return self.findRankr(A, B, i, j, s + l, t, r - l)
【在 A*******e 的大作中提到】
: 好像是算法导论的习题。不知标准答案是啥。
|
|
