一道华为的笔试题

Question

public class Neughbor{
private integer sourcecell;
private integer destcell;
public integer getsourcecell(){
return sourcecell;
}
public void setsourcecell(integer sourcecell){
this.sourcecell=sourcecell;
}
public integer getdestcell(){
return destcell;
}
public void setdestcell(integer destcell){
this.destcell=destcell;
}
}
业务描述：单项邻区：如果两个列表中存在一个sourcecell是n1、destcell是n2的neigbhor对象，并且在两个列表中不存在sourcecell是n2、destcell是n1的neighbor对象，则该neighbor对象就是单向邻区对象
输入：List<Neighbor>innerNbr;List<Neighbor>extNbr;
输出：打印出innernbr和extnbr列表中所有单向邻区对象
要求，当两个表的数据量很大时用最优的时间复杂度实现

Answer 1

打印出innernbr和extnbr列表中所有单向邻区对象

Answer 2

将innernbr里每一项的sourcecell和destcell调换位置，得到的就相当于extnbr吧？那这样子的话你可以用heap实现

Answer 3

对destcell建hash表,表中每一项指向一个sourcecell的hash链表.
然后遍历查找.时间复杂度最好情况下o(n),最坏情况下o(n2)大概是这样?

Answer 4

public static void main(String []args){ List <Neighbor> innerNbr =new ArrayList<Neighbor>();List <Neighbor> extNbr=new ArrayList<Neighbor>();innerNbr.add(new Neighbor());innerNbr.add(new Neighbor());innerNbr.add(new Neighbor());extNbr.add(new Neighbor());extNbr.add(new Neighbor());extNbr.add(new Neighbor());Iterator i=innerNbr.iterator(); Iterator j=extNbr.iterator(); while(i.hasNext()&&j.hasNext())){Neighbor n=(Neighbor)i.hasNext();Neighbor m=(Neighbor)j.hasNext();if(n.getsourcecell()==n1&&n.getdestcell()==n2&&m.getsourcecell()!=n2&&m.getdestcell()!=n1){System.out.println(n); System.out.println(m); }
}}