已知sum 在unsorted set中找两个数线性复杂度 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

已知sum 在unsorted set中找两个数线性复杂度

已知sum 在unsorted set中找两个数线性复杂度# JobHunting - 待字闺中

a*02013-11-06 08:11

1 楼

简单的解法知道set的range 产生一个int array ： int[range] 保证内容和
index一样（当然为了space可以红hash的版本此处不是讨论这个问题） sweep整个
set 看 sum-i是不是在array之中
但是如何克服一个corner situation？比如sum = 8 set之中只有一个4 这样自
己相当于用了两次
是不是加一个简单的判别如果sum=2i （当然这种情况必须运用hash了）看相应的bin
下是否有多于一个的i

c*t2013-11-06 08:11

2 楼

先排序 O(n)
然后从两头往中间扫，直到找到两个数和=sum或者两个index碰头了，这一步也是O(n)

bin

【在 a**********0 的大作中提到】

: 简单的解法知道set的range 产生一个int array ： int[range] 保证内容和
: index一样（当然为了space可以红hash的版本此处不是讨论这个问题） sweep整个
: set 看 sum-i是不是在array之中
: 但是如何克服一个corner situation？比如sum = 8 set之中只有一个4 这样自
: 己相当于用了两次
: 是不是加一个简单的判别如果sum=2i （当然这种情况必须运用hash了）看相应的bin
: 下是否有多于一个的i

a*02013-11-06 08:11

3 楼

如果扩展到找三个数whose sum 已知时间复杂度可以做到多少？

a*02013-11-06 08:11

4 楼

我觉得你的意思是用线性的sort
第二步骤是判断sum和两个指针的sum比谁的大如果sum大则左边指针向右移动否则右
边指针向左移动碰头就是没有

【在 c*****t 的大作中提到】

: 先排序 O(n)
: 然后从两头往中间扫，直到找到两个数和=sum或者两个index碰头了，这一步也是O(n)
:
: bin

c*t2013-11-06 08:11

5 楼

对
你的那个corner case也自动解决了

【在 a**********0 的大作中提到】

: 我觉得你的意思是用线性的sort
: 第二步骤是判断sum和两个指针的sum比谁的大如果sum大则左边指针向右移动否则右
: 边指针向左移动碰头就是没有

j*t2013-11-06 08:11

6 楼

这不就是2sum么，第一遍扫了放入hashmap，第二遍找hashmap中是否有target - val。
唯一要判断就是是否有值为target / 2。这个在放入hashmap的时候判断下就可以了。

r*l2013-11-06 08:11

7 楼

O(n)咋排序？

【在 c*****t 的大作中提到】

: 先排序 O(n)
: 然后从两头往中间扫，直到找到两个数和=sum或者两个index碰头了，这一步也是O(n)
:
: bin

i*e2013-11-06 08:11

8 楼

What is the set is really large?

t*r2013-11-06 08:11

9 楼

加count

bin

【在 a**********0 的大作中提到】

c*02013-11-06 08:11

10 楼

我一直不明白为什么要先全扫一遍再找，为什么不能先判断sum-a[i]存在不存在，如果
存在就找到了，如果不存在就是找不到，不就解决了？
for each i in a
{
if sum-a[i] exist in hash
found
else
not found
hash insert a[i]
}
这样不是边扫边找嘛。

y*32013-11-06 08:11

11 楼

什么排序可以做到O(n)？请指教

【在 c*****t 的大作中提到】

: 先排序 O(n)
: 然后从两头往中间扫，直到找到两个数和=sum或者两个index碰头了，这一步也是O(n)
:
: bin

o*r2013-11-06 08:11

12 楼

It's possible for some set of numbers, if:
1. size is relatively small
2. smallest and largest values are known
for example:
arr = [4, 6, 3, 0, 10]
you know that:
- smallest = 0,
- largest = 10
so you can create a int array of size 11:
temp = int[11] {};
for i in arr {
temp[i] = 1;
}
index of temp (having value of 1) contains the sorted 'arr'.

【在 y*****3 的大作中提到】

: 什么排序可以做到O(n)？请指教

m*f2013-11-06 08:11

13 楼

re

【在 c***0 的大作中提到】

: 我一直不明白为什么要先全扫一遍再找，为什么不能先判断sum-a[i]存在不存在，如果
: 存在就找到了，如果不存在就是找不到，不就解决了？
: for each i in a
: {
: if sum-a[i] exist in hash
: found
: else
: not found
: hash insert a[i]
: }

r*l2013-11-06 08:11

14 楼

有重复的怎么办？float怎么办？

【在 o*********r 的大作中提到】

: It's possible for some set of numbers, if:
: 1. size is relatively small
: 2. smallest and largest values are known
: for example:
: arr = [4, 6, 3, 0, 10]
: you know that:
: - smallest = 0,
: - largest = 10
: so you can create a int array of size 11:
: temp = int[11] {};

m*f2013-11-06 08:11

15 楼

why you guys choose to ignore what cc150 has suggested