📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 7534| 回复: 3
跳转到指定楼层
上一主题 下一主题
收起左侧

Google : 在一个数组中寻找三个数,使得它们的和为0

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
在一个数组中寻找三个数,使得它们的和为0

上一篇:Microsoft : 找出BST上任意节点的下一个节点
下一篇:《编译原理》到底是做什么的?
🔗
danielgao 2011-9-4 13:34:24 | 只看该作者
全局:
sort the array O(nlgn)

enumerate the first number, when the first number is fixed, use to two pointer to point to the start and the end of the array.

If the sum of the remaining two is greater than 0-first one then move the end pointer, other wise move the start pointer. O(n^2)

Total O(n^2)
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-9-5 00:08:59 | 只看该作者
全局:
sort the array O(nlgn)

enumerate the first number, when the first number is fixed, use to two pointer to point to the start and the end of the array.

If the sum of the remaining two is greater than 0-first one then move the end pointer, other wise move the start pointer. O(n^2)

Total O(n^2)
danielgao 发表于 2011-9-4 13:34


正确

  1. void Print3Sunm(int a[], int n)
  2. {
  3.         assert(a && n > 0);

  4.         sort(a, a + n);

  5.         for (int i = 0; i < n-2; i++)
  6.         {
  7.                 int nSum = -a[i];
  8.                 int p = i+1;
  9.                 int q = n-1;
  10.                 while (p < q)
  11.                 {
  12.                         if (a[p] + a[q] == nSum)
  13.                         {
  14.                                 cout<<a[i]<<" "<<a[p]<<" "<<a[q]<<endl;
  15.                                 return;
  16.                         }
  17.                         else if (a[p] + a[q] < nSum)
  18.                                 p++;
  19.                         else
  20.                                 q--;
  21.                 }
  22.         }

  23.         cout<<"Cannot find the number"<<endl;
  24. }
复制代码
回复

使用道具 举报

🔗
iveney 2011-9-9 22:37:00 | 只看该作者
全局:
本帖最后由 iveney 于 2011-11-7 09:43 编辑

我覺得解題不妨寫上思路,如果不是閱題無數,應該不能一下子想到好的解吧。至少我自己就要經歷一個優化的過程。劉未鵬的系列文章也提到類似問題。

另外一個好處是,據說面試提倡 "Think loud", 面試官也應該比較喜歡看到一個人思維的過程,並且逐步得到改進。

對於此題,最trivial的solution應該是枚舉2個數,算出他們的和,然後找這個和是否存在,O(n^3).
然後可以考慮如何加速找這個和,

1. 一個很自然的想法是排序后用二分查找,那麼可以優化為 O(nlogn + n^2 logn) = O(n^2 logn)。觀察到,如果對前兩個數的枚舉是有序遞增的,那麼他們的和也是 non-decreasing的。這時就可以 come out 到樓上的 solution.

2. 另外一种可能性,是把数组的数先hash起来,那么可以 O(1) 找到數組是否存在這個數。Insertion 也是 ~O(1) 的。那麼也是 O(n + n^2) = O(n^2)
Update: 今天剛好看到了一篇對 3-SUM 的介紹:http://www.cs.mcgill.ca/~jking/papers/3sumhard.pdf
有興趣可以看看。這個問題就是 3-SUM 本身。另外一道流行的面試題是問給出一堆點,問裡面有沒有三點共線 (colinear)。
這個問題可以 reduce 到 3-SUM.
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表