-1

我正在做一个项目，我必须合并和相交两组。我为每个带有虚拟节点的集合使用链接列表。这就是我初始化我的 Sets LL 类的方式

public Set() {
 top = new Node(Integer.MIN_VALUE, new Node(Integer.MAX_VALUE, null) );
} //end Set

这就是我插入项目的方式。

public void insert(int item) {
 Node prev = top;
 Node curr = top.next;

 while( curr.item < item ) {
  prev = curr;
  curr = curr.next;
 }
 prev.next = new Node( item, curr);
 size++;
} // insert

现在我发现很难得到两个集合的并集或交集。这就是我对交叉点的想法。

public Set intersection( Set setB ) {
 Set setC = new Set ();
 //loop over both sets and if both have same value add it otherwise 
 // get to the next node in both sets.

我的问题是，我的交集伪代码在逻辑上是否正确？我的联合伪代码虽然可笑。谁能指导我解决这个问题？

4

1 回答 1

0

对于这个简单的输入，您的想法将失败：

1  2
2  3

你的想法：

//loop over both sets and if both have same value add it otherwise 
// get to the next node in both sets.
  • 第一次迭代 - 我们有1和2，不同的值，所以我们在两组中都进入下一个
  • 第二次迭代 - 我们有2和3，不同的值，所以进入下一个
  • 结尾

你真正需要的是：

  • 在不匹配时，仅推进具有较低元素的列表
  • 匹配时，添加到结果并推进两者（或删除重复项，只要重复相同的值，就继续推进两者）

对于 union，这个想法非常相似：

  • 在不匹配时，添加较低的元素并推进包含较低元素的列表
  • 在匹配时，添加并推进两者（或者只要重复相同的值就继续推进）
于 2017-02-20T19:22:46.293 回答