1

我有一个项目的数组列表，每个项目都有一个将任何其他项目作为参数的方法。确保我在每对可能的项目上调用该方法而不重复它们的最有效方法是什么？（可以假设所有项目都是唯一的）。

我的代码：

public boolean hasConflict (ArrayList<Item> items) {
    // For every possible pair of items...
        one = items.get(i);
        two = items.get(j);

        if ( one.conflictsWith (two)) {
            return true;
        }

    // If we reach the end of the list without finding a conflict
    return false;
}

编辑：

one.conflictsWith (two)将返回与 相同的值two.conflictsWith (one)，很抱歉忘记了这一点。

该conflictsWith方法没有比较两个值是否重复，所以很遗憾我不能使用哈希表对其进行排序。

4

3 回答 3

3

如果您不需要打电话a.conflictsWith(b)很简单，因为b.conflictsWith(a)您可以通过以下方式节省一些时间：

for(int i = 0; i < list.size(); ++i) {
    final MyClass curr = list.get(i);
    for(int j = i + 1; j < list.size(); ++j) {
        curr.conflictsWith(list.get(j));
    }
}

即循环遍历List，然后在第二个循环中循环遍历.List

否则，您需要遍历所有内容

for(int i = 0; i < list.size(); ++i) {
    final MyClass curr = list.get(i);
    for(int j = 0; j < list.size(); ++j) {
        if(i != j) {
            curr.conflictsWith(list.get(j));
        }           
    }
}
于 2013-10-14T16:07:06.987 回答
1

如果conflictsWith()是对称的，即one.conflictsWith(two) == two.conflictsWith(one)对于每对参数，则使用：

for (int i = 0; i < items.size(); i++)
{
    final Item one = items.get(i);
    for (int j = i + 1; j < items.size(); j++}
    {
        one.conflictsWith(items.get(j));
    }
}

如果它不是对称的，则必须再检查 2 次：

for (int i = 0; i < items.size(); i++)
{
    final Item one = items.get(i);
    for (int j = 0; j < items.size(); j++} // only this line changed
    {
        one.conflictsWith(items.get(j));
    }
}

最后一个也会检查one.conflictsWith(one)。如果这是一个问题，请使用 if (i != j).

于 2013-10-14T16:07:46.773 回答
1

由于我们不知道“冲突”是什么意思，例如，如果a.conflictsWith(b)说a. conflictsWith(c)s.th about b.conflictsWith(c)，你必须触及每一个组合，即

   for(int i=0; i< items.size(); i++) {
     Item item = items.get(i);
     for(int j=0; j< items.size(); j++)
       if(item.conflictsWith(items.get(j)) return true;
     }
   }
   return false;

如果关系 conflictWith 是对称的并且如果 a.conflictsWith(a) 始终为假，则可以使用

   for(int i=0; i< items.size(); i++) {
     Item item = items.get(i);
     for(int j=i+1; j< items.size(); j++)
       if(item.conflictsWith(items.get(j)) return true;
     }
   }
   return false;
于 2013-10-14T16:08:46.390 回答