用于查找列表元素之间冲突的相对顺序的算法

Question

我不知道这个问题的名称(如果我知道，我可能会找到解决方案(。

问题：

给定两个整数列表，A 和 B，确定任何两个元素x和y之间是否存在排序冲突，其中x和y都存在于A和B中。

例如，请考虑以下两个列表：

A : 2 3 8 9
B : 3 1 7 2

在这种情况下，存在排序冲突{ 2, 3 }因为这些元素在列表A中以相反的顺序显示，就像它们在列表B中一样。

琐碎案例

A和B没有共同的元素;没有冲突。

A和B是同一个列表;没有冲突。

问题

解决这个问题

有哪些算法？

Answer 1

编辑：

在这种情况下，

1. 在两个列表中创建公共元素的有序列表(按列表 2 排序(
2. 使用新列表，执行相同的操作，创建常见元素的有序列表(按列表 1 排序(。
3. 检查两个列表是否相同。

若要创建有序列表，请在其他列表中搜索要设置顺序的列表中的每个元素。 如果找到，请将其添加到新列表中。

这将是 O(n*m(。

您还必须检查不相邻的重复项，这可以在创建新列表时完成。

Answer 2

不确定这是否是最佳的，但以下是一种解决方法：-

1. 创建一个 A 和 B 的交集，称之为 C
2. C 的元素具有属性(索引 A、索引 B(
3. 当我们遍历 C 元素时，indexA 和 indexB 都应该减少或增加。如果索引 A 在增加，而 indexB 在减少，那么我们就有一个冲突的相对顺序。

例如：

  A : 2 3 8 9
  B : 3 1 7 2
  C : 2(1,4),3(2,1)

正如我们所看到的，索引A在增加，而索引B在减少，所以存在冲突。

Answer 3

创建一个哈希(或任何快速查找数据结构(，其中键作为第一个数组中的值，值作为数组中的索引(位置(。让我们称之为S

def Validate(A, B):
    S = CreateLookupTable(A)
    minValueTillNow = -∞
    for i in B:
      if i in S:
         indexInA = lookup(S, i)
         if indexInA < minValueTillNow:
            return false
         minValueTillNow = indexInA
    return true

Answer 4

您尚未提供详细信息，但正如现在所述，可以在 O(n( 中完成：

int[] A = new[] {2, 8, 9, 10, 3};
int[] B = new[] {2, 1, 7, 3};
int x = 2, y = 3;
int a1 = -1, a2 = -1, b1 = -1, b2 = -1;
for (int i = 0; i < (A.Length > B.Length ? A.Length : B.Length); i++)
{
    if (a1 == -1 && A.Length > i && A[i] == x) a1 = i;
    if (a2 == -1 && A.Length > i && A[i] == y) a2 = i;
    if (b1 == -1 && B.Length > i && B[i] == x) b1 = i;
    if (b2 == -1 && B.Length > i && B[i] == y) b2 = i;
    if (a1 >= 0 && a2 >= 0 && b1 >= 0 && b2 >= 0) 
        break;
}
var result = (a1 < a2) == (b1 < b2) && ((a1 == -1 && b1 == -1) || (a1 != -1 && b1 != -1));

您只遍历一次数组，直到数组结束或直到分配所有变量。然后是一个简单的检查顺序是否相同。

Answer 5

1. 获取两个列表之间的所有公共元素值

2. 创建 2 个列表，其中仅包含按其排序的常见元素各自的源列表(由各自的来源列表(

3. 通过删除命令器将这些列表仅减少到无序元素从我们正在测试的列表中列出元素(仅保留我们正在测试的列表中的"无序"元素(

数据结构做了很多工作。 因此，了解他们每个人的能力很重要。 简而言之，set 按原样处理值，而列表考虑排序 AND 值。我们可以通过使用LinkedHashSet变得更加疯狂，或者用bitset做一些疯狂的事情并添加漂亮的lambda，但希望这很简单。

示例代码

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class OrderingEnforcer {
    public static List<Integer> getImproperlyOrderedElements(List<Integer> ordinator, List<Integer> toTest) {
        // create a distinct intersection of a and b (order insensitive)
        Set<Integer> intersection = new HashSet<Integer>(ordinator);
        intersection.retainAll(new HashSet<Integer>(toTest));
        // create a sorted list of our intersected set using the
        // indexOf(element)
        // to determine the list ordering
        List<Integer> ordinatorOrderedIntersection = new ArrayList<Integer>(intersection);
        Collections.sort(ordinatorOrderedIntersection, createIndexComparator(ordinator));
        List<Integer> toTestOrderedIntersection = new ArrayList<Integer>(intersection);
        Collections.sort(toTestOrderedIntersection, createIndexComparator(toTest));
        // Now we can create a difference of the two Lists
        toTestOrderedIntersection.removeAll(ordinatorOrderedIntersection);
        return toTestOrderedIntersection;
    }
    private static Comparator<Integer> createIndexComparator(List<Integer> list) {
        return (a, b) -> {
            return Integer.compare(list.indexOf(a), list.indexOf(b));
        };
    }
}