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

Google Intern: find reverse pair in two arrays

🔗
 楼主| Imbalism 2011-10-5 04:18:20 | 只看该作者
全局:
回复 10# wwwyhx


   是直接学校面试
回复

使用道具 举报

🔗
ilhrx 2011-10-5 09:27:05 | 只看该作者
全局:
如果需要打印所有的pairs的确只有n^2的方法
如果只是找出 the number of pairs , 可以利用二叉树来降低到O(n logn )

sq[i]表示A2[i]在A1中出现的位置
对A2建立二叉树, 从n到1 ,依次按照sq[i]为关键值插入二叉树
那么对于插入的元素A2[i]来说,以它为开头的pairs的数量,等于当前二叉树中sq值比它小的数量。
时间复杂度为O(n logn )
回复

使用道具 举报

🔗
imwmwm 2011-10-13 14:27:38 | 只看该作者
全局:
  1. private static void solution1(int[] a1, int[] a2){
  2. for(int i = 0; i < a2.length; i++){
  3.                         for(int j = i + 1; j < a2.length; j++){
  4.                                 if(solution1_findIndex(a1, a2[j]) != -1 &&
  5.                                                 solution1_findIndex(a1, a2[j]) < solution1_findIndex(a1, a2[i])){
  6.                                         System.out.println(a2[i] + ", " + a2[j]);
  7.                                 }
  8.                         }
  9.                 }
  10.         }
  11.        
  12.         private static int solution1_findIndex(int[] a1, int b){
  13.                 for(int i = 0; i < a1.length; i++){
  14.                         if(a1[i] == b){
  15.                                 return i;
  16.                         }
  17.                 }
  18.                 return -1;
  19.         }
复制代码
随便写了个暴力法 明天再说
回复

使用道具 举报

🔗
wwwyhx 2011-11-4 01:35:10 | 只看该作者
全局:
简单写了一下,假定两个数组等长,且元素都为正整数:
burself 发表于 2011-11-3 19:00


写这么长的代码时间肯定不够
回复

使用道具 举报

🔗
lambda2fei 2012-9-3 13:13:04 | 只看该作者
全局:
要全部输出最坏复杂度O(n^2),若只求个数就是简单的逆序对个数吧。
回复

使用道具 举报

🔗
CStick75 2012-9-6 22:00:57 | 只看该作者
全局:
burself 发表于 2011-11-3 19:04
看题目给的例子,貌似只要求比较数组二中相邻的元素?
如果是那样的话,rank_b可以把数组一中没有的元素也 ...

不是吧,特例而已……这个最多的时候可以有N*(N-1)/2对……所以 worst case 不能比O(N^2)再少了
回复

使用道具 举报

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

本版积分规则

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