b******b 发帖数: 300 | 1 已知一个sorted的array,怎么找到第一个pair的两个数,其之和为N。
我想到的使用hash,提示说binary search tree更好……没想到idea。
求教 |
i***h 发帖数: 12655 | |
b******b 发帖数: 300 | 3 为什么是nlgn, 已经sorted了。
我觉得关键他要求的是第一个。。。这个不知道该怎么处理
【在 i***h 的大作中提到】 : hash是O(N) : BST要O(NlgN)吧?
|
d****o 发帖数: 1055 | 4 输入和输出再定义清楚。
输入是什么,输出是什么?
给个例子。
【在 b******b 的大作中提到】 : 已知一个sorted的array,怎么找到第一个pair的两个数,其之和为N。 : 我想到的使用hash,提示说binary search tree更好……没想到idea。 : 求教
|
l*****a 发帖数: 14598 | 5 他的提示也不对啊
已经有序就首尾找。。
【在 b******b 的大作中提到】 : 已知一个sorted的array,怎么找到第一个pair的两个数,其之和为N。 : 我想到的使用hash,提示说binary search tree更好……没想到idea。 : 求教
|
i***h 发帖数: 12655 | 6 你在排序里面二分法找一个数不得 O(lgN)?
【在 b******b 的大作中提到】 : 为什么是nlgn, 已经sorted了。 : 我觉得关键他要求的是第一个。。。这个不知道该怎么处理
|
d**e 发帖数: 6098 | 7 这个不应该是一头一尾两个index移动吗?
【在 b******b 的大作中提到】 : 已知一个sorted的array,怎么找到第一个pair的两个数,其之和为N。 : 我想到的使用hash,提示说binary search tree更好……没想到idea。 : 求教
|
b******b 发帖数: 300 | 8 输入是一个sorted的数组
1,2,3,3,4,5.。。。
如果要求两个数之和为6,
输出为 3 ,3
【在 d****o 的大作中提到】 : 输入和输出再定义清楚。 : 输入是什么,输出是什么? : 给个例子。
|
i***h 发帖数: 12655 | 9 哦是你对, 这样一来只要O(N)
还是和BST没关系
【在 d**e 的大作中提到】 : 这个不应该是一头一尾两个index移动吗?
|
h*****y 发帖数: 218 | 10 我也觉得如此,难道我题目没有看明白?
【在 d**e 的大作中提到】 : 这个不应该是一头一尾两个index移动吗?
|
|
|
i***h 发帖数: 12655 | 11 为什么不是1,5?
【在 b******b 的大作中提到】 : 输入是一个sorted的数组 : 1,2,3,3,4,5.。。。 : 如果要求两个数之和为6, : 输出为 3 ,3
|
b******b 发帖数: 300 | 12 因为 相比于1,5,
3,3 是最早完整出现的
原谅我的表达吧。。。。实在是表述不清楚了
【在 i***h 的大作中提到】 : 为什么不是1,5?
|
i***h 发帖数: 12655 | 13 我知道了
用BST 找 6/2
然后中心开花向外找
【在 b******b 的大作中提到】 : 因为 相比于1,5, : 3,3 是最早完整出现的 : 原谅我的表达吧。。。。实在是表述不清楚了
|
d**e 发帖数: 6098 | 14 真的不是很明白
不过可以在于你从哪里数起
我觉得应该从1开始数
【在 b******b 的大作中提到】 : 因为 相比于1,5, : 3,3 是最早完整出现的 : 原谅我的表达吧。。。。实在是表述不清楚了
|
b******b 发帖数: 300 | 15 恩,恩,就是从1开始数起
【在 d**e 的大作中提到】 : 真的不是很明白 : 不过可以在于你从哪里数起 : 我觉得应该从1开始数
|
d**e 发帖数: 6098 | 16 我明白题目的意思了。
谢谢。
【在 b******b 的大作中提到】 : 恩,恩,就是从1开始数起
|
b******b 发帖数: 300 | 17 这样是不是还得取决于建立一个结构良好的二叉树?
如果二叉树是个高度为n的二叉树,计算复杂度也不低啊
【在 i***h 的大作中提到】 : 我知道了 : 用BST 找 6/2 : 然后中心开花向外找
|
d**e 发帖数: 6098 | 18 我觉得前面有同学说的正确
用hash就是O(n)空间,O(n)时间
用bst是O(1)空间,O(nlgn)时间
【在 b******b 的大作中提到】 : 恩,恩,就是从1开始数起
|
i***h 发帖数: 12655 | 19 排序数组本身就是一个平衡BST啊
【在 b******b 的大作中提到】 : 这样是不是还得取决于建立一个结构良好的二叉树? : 如果二叉树是个高度为n的二叉树,计算复杂度也不低啊
|
i***h 发帖数: 12655 | 20 对这个问题, 时间是 O(lgN + N), 也是O(N)
【在 d**e 的大作中提到】 : 我觉得前面有同学说的正确 : 用hash就是O(n)空间,O(n)时间 : 用bst是O(1)空间,O(nlgn)时间
|
|
|
i***h 发帖数: 12655 | 21 不过最坏情况还没从头开始找好...
【在 i***h 的大作中提到】 : 对这个问题, 时间是 O(lgN + N), 也是O(N)
|
b******b 发帖数: 300 | 22 对哦,一下糊涂了,汗……
【在 i***h 的大作中提到】 : 排序数组本身就是一个平衡BST啊
|
y**********u 发帖数: 6366 | 23 移动的过程可以用binary search
【在 d**e 的大作中提到】 : 这个不应该是一头一尾两个index移动吗?
|
y**********u 发帖数: 6366 | 24 hash 显然有worst case啊
【在 d**e 的大作中提到】 : 我觉得前面有同学说的正确 : 用hash就是O(n)空间,O(n)时间 : 用bst是O(1)空间,O(nlgn)时间
|
d**e 发帖数: 6098 | 25 我好像跟我之前遇到的题混了一下,但这样似乎也是O(n)?
for each x in the array
map(x) = N-x
index_end = -1
for i in 0..n-1
if exists map(map(array_i))
if index_end == -1
index_end = n-1-i
else
index_end = min(index_end, n-1-i)
if index_end != -1
return (n-1-index_end, index_end)
【在 y**********u 的大作中提到】 : hash 显然有worst case啊
|
y*****n 发帖数: 243 | 26 头一个指针从左到右找。然后通过binary search 找另一个数。worse case是olgn. |
d******y 发帖数: 244 | 27 头一个指针从左到右找。然后通过binary search 找另一个数。
It makes sense, pointer + a sorted numbers
worse case是olgn.
How can get this? |
y*****n 发帖数: 243 | 28 = =刚刚二B了- -worse case还是O(n)吧
【在 d******y 的大作中提到】 : 头一个指针从左到右找。然后通过binary search 找另一个数。 : It makes sense, pointer + a sorted numbers : worse case是olgn. : How can get this?
|
y*****n 发帖数: 243 | 29 I made it wrong again, it should be nlog(n)
log(n-1)+log(n-2)+....log(1) = log((n-1)*log(n-2)*...log(1))
=O(nlog(n))
Hope it is right this time
【在 d******y 的大作中提到】 : 头一个指针从左到右找。然后通过binary search 找另一个数。 : It makes sense, pointer + a sorted numbers : worse case是olgn. : How can get this?
|
r*******n 发帖数: 266 | 30 O(N)
【在 b******b 的大作中提到】 : 已知一个sorted的array,怎么找到第一个pair的两个数,其之和为N。 : 我想到的使用hash,提示说binary search tree更好……没想到idea。 : 求教
|
|
|
d******y 发帖数: 244 | 31 log(n-1)+log(n-2)+....log(1) = log((n-1)*log(n-2)*...log(1))
=O(nlog(n))
this one should be
log(n-1)+log(n-2)+....log(1) = log((n-1)(n-2)...(1))
log(n-1) O(nlog(n))
Is this right? |
b***u 发帖数: 12010 | 32 不好用吧?一个heap容易用数组表示,可用sorted array的话,root和child index的
关系不容易表达。
这题从左到右每个对后面进行binary search就行,找到N/2还没有就没了。O(nlogn).
【在 i***h 的大作中提到】 : 排序数组本身就是一个平衡BST啊
|
g**u 发帖数: 504 | 33 Imput:
array A, sum s.
Output:
pair (u,v)
Given an sorted array, choose the middle element m, then m is the root of a
balanced BST. If s-m>m, we search the right sub-tree, otherwise we search
the left sub-tree. Doing this recursively, we can find (u,v) in O(log(n)).
【在 b******b 的大作中提到】 : 输入是一个sorted的数组 : 1,2,3,3,4,5.。。。 : 如果要求两个数之和为6, : 输出为 3 ,3
|
g**u 发帖数: 504 | 34 哦,不好意思,这个不对,有可能 u 在 left subtree,而 v 在 right subtree
a
【在 g**u 的大作中提到】 : Imput: : array A, sum s. : Output: : pair (u,v) : Given an sorted array, choose the middle element m, then m is the root of a : balanced BST. If s-m>m, we search the right sub-tree, otherwise we search : the left sub-tree. Doing this recursively, we can find (u,v) in O(log(n)).
|
y**********u 发帖数: 6366 | 35 这个map是什么数据结构?
如果是array的话,小心越界。如果是hash或者bst的话,不止O(n)了
【在 d**e 的大作中提到】 : 我好像跟我之前遇到的题混了一下,但这样似乎也是O(n)? : for each x in the array : map(x) = N-x : index_end = -1 : for i in 0..n-1 : if exists map(map(array_i)) : if index_end == -1 : index_end = n-1-i : else : index_end = min(index_end, n-1-i)
|
r*******n 发帖数: 266 | 36 这题牙根就不用神马BST
有一道很出名的题, 给一个2-d array, 冲右冲下都是递增的, 怎么找其中的某个
element...答案是从右上角开始一步一步走, O(n)时间
看着眼熟不?
【在 b******b 的大作中提到】 : 已知一个sorted的array,怎么找到第一个pair的两个数,其之和为N。 : 我想到的使用hash,提示说binary search tree更好……没想到idea。 : 求教
|
h********w 发帖数: 221 | |