科普一下这次BP的漏油事故 (转载) - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Stock

科普一下这次BP的漏油事故 (转载)

科普一下这次BP的漏油事故 (转载)# Stock

g*c2010-07-02 07:07

1 楼

我在网上找了个答案
http://yucoding.blogspot.in/2012/12/leetcode-question-3-4-sum.h
他先是把所有元素两两相加，存进multimap做了个hash，
然后在这个multimap里依次两两相加看是否等于target。
我感觉他的解法很费时间啊，超过O(n^4)了吧？（因为首先构建好multimap的size是O(
n^2)，然后再两层for循环）
我之前用3sum那种方法写的，左右移动指针，O(n^3)，不超时，但是最近提交都显示超
时。
哪里有不超时C++的答案呢？

c*72010-07-02 07:07

2 楼

【以下文字转载自 Military 讨论区】
发信人: churchance (吃橙子), 信区: Military
标题: Re: 有没有石油大牛科普一下这次BP的漏油事故啊
发信站: BBS 未名空间站 (Fri Jul 2 12:04:48 2010, 美东)
发信人: Yesterday (yesterday), 信区: Texas
标题: Re: 有没有石油大牛科普一下这次BP的漏油事故啊
发信站: BBS 未名空间站 (Fri Jul 2 00:41:53 2010, 美东)
This is what I heard how it happened.
1. The accident started from a gas bubble in the well, and this is normal in
drilling or production wells.
2. As the gas bubble traveled up, it inflated (pressure decreases, volume
increases, temperature dro

c*02010-07-02 07:07

3 楼

这个代码O(n^3), 但不超时。
vector > fourSum(vector &num, int target) {
vector > rst;
if(num.size() <= 3) return rst;
std::sort(num.begin(), num.end());

int len = num.size();
for(int i = 0; i < num.size() - 3; i++){
if(i > 0 && num[i] == num[i-1]) continue;
for(int j = i + 1; j < num.size() - 2; j++){
if(j > i + 1 && num[j] == num[j-1])continue;
int l = j + 1, r = len - 1;
while(l < r){
int sum = num[i] + num[j] + num[l] + num[r] ;
if(sum == target){
vector item = {num[i], num[j], num[l], num[r]};
rst.push_back(item);
r--;
while(l < r && num[r] == num[r+1]) r--;
l++;
while(l < r && num[l] == num[l-1]) l++;
}else if(sum > target)
r--;
else
l++;
}
}
}
return rst;
}

g*c2010-07-02 07:07

4 楼

有没有O（n^2 * lg n）的代码呢？网上都说自己的复杂度低，可是一看都很高

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

: 这个代码O(n^3), 但不超时。
: vector > fourSum(vector &num, int target) {
: vector > rst;
: if(num.size() <= 3) return rst;
: std::sort(num.begin(), num.end());
:
: int len = num.size();
: for(int i = 0; i < num.size() - 3; i++){
: if(i > 0 && num[i] == num[i-1]) continue;
: for(int j = i + 1; j < num.size() - 2; j++){