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

Google : 两个排序数组中求第k大的sum(a+b)

 
🔗
xusi 2013-7-24 01:19:53 | 只看该作者
全局:
  1. 你们说的好深奥,是不是这个意思,如果a,b是这样:
  2. A: 1 2 3 4
  3. B: x y z w

  4. A为1的组合: (1+x) (1+y) (1+z) (1+w)
  5. A为2的组合: (2+x) (2+y) (2+z) (2+w)
  6. A为3的组合: (3+x) (3+y) (3+z) (3+w)
  7. A为4的组合: (4+x) (4+y) (4+z) (4+w)

  8. 如果是要从所有a+b的组合中找出第k个,那把上面4行看成4个有序数组,用merge sort的方法得到第k个元素应该就是想要的结果吧。可以用heap来选择n个队头中的min,heap node只要保存队头的值,A指针和B指针,每次取出最小值后,让B指针指向下一个,如果队伍空则delete node,否则更新队头的值,然后维护一下heap。这样空间是O(n), 时间是O(n+klogn),不知对不对?
复制代码
回复

使用道具 举报

🔗
muzac 2013-12-11 20:29:32 | 只看该作者
全局:
用一个最小堆就行了吧0 0
开始a(i)+b(0)入堆 以后每次弹出a(i)+b(j)时 入堆a(i)+b(j+1)
j的值可另开一数组对每个i维护自己的j值
回复

使用道具 举报

🔗
deeper99 2013-12-12 06:31:05 | 只看该作者
全局:
//The solution could be:
flag = A;
while( true )
{
    if(A[i] > B[j]){
        list.Add(B[j]);
                flag = B;
        j++;
    }else{
        list.Add(A[i]);
                flag = A;
        i++;
    }
        if(i*j>k){
                a = (flag==A)? A[i] : A[p];
                b = (flag==B)? B[j] : B[p];
                return sum(a, b);
        }else if(i*j==k){
                return sum(A[i],B[j]);
        }else{
                p = k-i*j;
        }
}
回复

使用道具 举报

🔗
benjamin2037 2013-12-28 18:39:04 | 只看该作者
全局:
我有一个想法,不知道对不对供大家参考。
回复

使用道具 举报

🔗
iamzhaiwei 2013-12-28 20:46:18 | 只看该作者
全局:
我认为,9楼的解法是正确的,不知道有没有更好的方法
回复

使用道具 举报

🔗
benjamin2037 2013-12-28 22:05:48 | 只看该作者
全局:
我的算法,空间多用一个长度为k的数组c,这个数组有一个功能是每次在队列尾部添加数据的时候会自动排序。
1,轮流去 a组与b组中较小的数据
2,取到的数据与另外一个数组中已经取过的每个数据求和,加入C数组尾部。
3重复1,2步直到第k个元素加入数组c,
4,取出数组第k个元素。就是答案,时间复杂度应该是k+k次插入数组c的开销。
因为数组c是迭代生成已经是排序好的,所以因为性能会很好。
欢迎大家讨论。
回复

使用道具 举报

🔗
iamzhaiwei 2013-12-28 22:13:11 | 只看该作者
全局:
回复

使用道具 举报

🔗
jiebour 2015-7-16 22:08:14 | 只看该作者
全局:
这个题其实就是leetcode里面merge K sorted list的变体,仔细想想就明白了。

K远远小于M,N(分别为A,B数组的长度)的话,那么复杂度就是 K*lgK。
若不是,复杂度就是K*lg(Min(M, N))
回复

使用道具 举报

🔗
zhuli19901106 2015-7-16 22:55:39 | 只看该作者
全局:
就是这道题:http://ac.jobdu.com/problem.php?pid=1534
从这数据看貌似期望的解是O(n * logn)的,O(K)应该不行。这是ac的代码:
  1. #include <algorithm>
  2. #include <cstdio>
  3. #include <cstring>
  4. using namespace std;

  5. typedef long long int LL;
  6. const int N = 100005;
  7. LL a[N], b[N];
  8. int m, n;
  9. LL k;

  10. LL count(int mm)
  11. {
  12.     LL cc = 0;
  13.     int i, j;

  14.     j = n - 1;
  15.     for (i = 0; i < m; ++i) {
  16.         while (j >= 0 && a[i] + b[j] > mm) {
  17.             --j;
  18.         }
  19.         cc += (j + 1);
  20.     }

  21.     return cc;
  22. }

  23. int solve()
  24. {
  25.     LL ll = a[0] + b[0];
  26.     LL rr = a[m - 1] +b[n - 1];
  27.     LL mm;

  28.     while (ll <= rr) {
  29.         mm = (ll + rr) / 2;
  30.         if (k <= count(mm)) {
  31.             rr = mm - 1;
  32.         } else {
  33.             ll = mm + 1;
  34.         }
  35.     }

  36.     return ll;
  37. }

  38. int main()
  39. {
  40.     int i;

  41.     while (scanf("%d%d%lld", &m, &n, &k) == 3) {
  42.         for (i = 0; i < m; ++i) {
  43.             scanf("%lld", &a[i]);
  44.         }
  45.         for (i = 0; i < n; ++i) {
  46.             scanf("%lld", &b[i]);
  47.         }
  48.         sort(a, a + m);
  49.         sort(b, b + n);

  50.         printf("%lld\n", solve());
  51.     }

  52.     return 0;
  53. }
  54. /**************************************************************
  55.     Problem: 1534
  56.     User: zhuli19901106
  57.     Language: C++
  58.     Result: Accepted
  59.     Time:840 ms
  60.     Memory:2584 kb
  61. ****************************************************************/
复制代码
回复

使用道具 举报

🔗
zhuli19901106 2015-7-16 23:00:43 | 只看该作者
全局:
本帖最后由 zhuli19901106 于 2015-7-17 01:44 编辑
jiebour 发表于 2015-7-16 22:08
这个题其实就是leetcode里面merge K sorted list的变体,仔细想想就明白了。

K远远小于M,N(分别为A,B ...

同意,之前没想到这点。
回复

使用道具 举报

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

本版积分规则

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