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

Google Intern : two sorted array 中,求和等于指定数的组合

全局:

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

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

x
两个排好序的数组A, B.和一个数c, 求a + b = c, a属于A, b属于B

上一篇:Google : 找出穿过点最多的直线
下一篇:facebook : Print the largest number within a moving window
🔗
2339923 2011-8-12 11:27:39 | 只看该作者
全局:
用c分别减去数组B里面的数,c-B[1],,,,c-B[n],每减一次得到一个值x,用二分查找法找出A数组里面的a。。

感觉这个想法弱爆啊。不过能力有限。。也就只能想到这个方法了
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-8-12 11:51:06 | 只看该作者
全局:
用c分别减去数组B里面的数,c-B[1],,,,c-B[n],每减一次得到一个值x,用二分查找法找出A数组里面的a。。

感觉这个想法弱爆啊。不过能力有限。。也就只能想到这个方法了
2339923 发表于 2011-8-12 11:27



    和在一个sorted array里找类似吧,如果是两个sorted array我想还是和一个sorted array一样两边夹. 一个pointer指向数组A的最小 says pA, 另一个pB指向数组B的最大, 然后两边夹直到*pA > *pB.
然后pA指向A的最大,pB指向B的最小再来一次.
回复

使用道具 举报

🔗
coder 2011-8-18 04:47:26 | 只看该作者
全局:
按楼主的算法写的。

public class Two_sorted_array_sum {
        private int[] a;
        private int[] b;
        public int i,j;//pointers to array a,b;
        private int sum;
        public Two_sorted_array_sum(int[] a, int[] b, int sum) {
                // TODO Auto-generated constructor stub
                this.a=a;
                this.b=b;
                this.sum=sum;
                i=0;
                j=b.length-1;
                if(!find(a,b)){
                        find(b,a);
                }
        }
        public boolean find(int[] front, int[] end){
                for(int k=0; k<end.length; k++){
                        if(front[i]+end[j]<sum)
                                i++;
                        else if(front[i]+end[j]>sum)
                                j--;
                        else
                                return true;
                }
                return false;
        }

        public static void main(String[] args) {
                // TODO Auto-generated method stub
                int[] a={3,5,7,8,10};
                int[] b={2,4,5,6,8,9};
                Two_sorted_array_sum test=new Two_sorted_array_sum(a,b,17);
                System.out.println(test.i);
                System.out.println(test.j);
        }
}
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-8-18 12:55:23 | 只看该作者
全局:
c++版

  1. bool GetSum(int A[], int n, int B[], int m, int c, int& ia, int& ib)
  2. {
  3.         assert(A && n > 0 && B && m > 0);

  4.         ia = n-1;
  5.         ib = 0;
  6.         while (ia >= 0 && ib < m && A[ia] >= B[ib])
  7.         {
  8.                 if (A[ia] + B[ib] == c)
  9.                         return true;

  10.                 if (A[ia] + B[ib] < c)
  11.                         ib++;
  12.                 else
  13.                         ia--;
  14.         }

  15.         ia = 0;
  16.         ib = m-1;
  17.         while (ia < n && ib >= 0 && B[ib] >= A[ia])
  18.         {
  19.                 if (A[ia] + B[ib] == c)
  20.                         return true;

  21.                 if (A[ia] + B[ib] < c)
  22.                         ia++;
  23.                 else
  24.                         ib--;
  25.         }

  26.         return false;
  27. }
复制代码
回复

使用道具 举报

🔗
xiayuan0623 2011-9-24 02:50:37 | 只看该作者
全局:
Good.

Just wrote this several days before...
回复

使用道具 举报

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

本版积分规则

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