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 | |
