访谈问:确定数据流中的唯一配对

Question

这是一个面试问题,我想知道是否有更好的方法来解决这个问题.我有一长串数据说,[(A,1),(B,2),(A,2),(B,1),(A,3),(A,4),(B,4) ),....]等等.这里,(A,1)与(B,1)配对.(A,2)与(B,2)对配对.在流(长度未知)中,将有一个项目没有一对,如上例中的(A,3).保证只有1个没有一对.如何确定哪一项是1项？

我的方法是有2个地图 - 1个用于A,1个用于B用整数键.根据流中的A或B,我会检查其他地图中是否存在特定的密钥,如果条目存在,我会删除该条目,否则我会将该对添加到它所属的相应地图中.最后,我检查了两张地图,看看哪一张有左对.

我觉得可能有更好的方法.请告诉我.

class Pair {
    Integer value;
    String collectionName;
}

class Stream {
    public Pair getNext();
    public boolean hasNext();
}

public Pair findUniquePair(Stream s) {
    ....
}

我不得不实施

findUniquePair()方法

更新:抱歉,我之前将boolean作为返回类型.现在我完全记住了这个问题,我确实必须返回一对.但不一定必须是同一个对象.我相应地更新了方法的返回类型.

Answer 1

这仅在存在"仅一个非配对项目"保证时才起作用:将int结果初始化为零,并逐项遍历流.对于每个项目XOR,结果为值.到达流的末尾时,结果将设置为唯一项.您可以忽略集合名称,没有必要:

Stream s = ...
while (s.hasNext()) {
    Pair p = s.getNext();
    res ^= p.getValue();
}

这个技巧起作用的原因是int对相同值进行两次异或运算会使该值保持不变.您应用XOR的顺序无关紧要,因为所有配对的XOR最终会相互抵消.

我现在记得我必须为该方法返回一对.它可以是一个新的Pair对象,不一定是同一个对象.

要弄清楚要返回什么名称,"A"或者"B"做一个简单的计数器.当你看到一个"A",加1; 当你看到"B",减去1.继续对值进行相同的XOR.

一旦到达流的末尾,计数器将是正数或负数(但不是零).如果是积极的,我们有一个不成对的"A"; 否则我们有一个未配对的"B".