java 多个列表中的公共元素

e1xvtsh3  于 2023-01-07  发布在  Java
关注(0)|答案(3)|浏览(145)

我需要在多个预先排序的列表中找到所有的公共元素(如果所有列表中都存在重复项,那么它们必须被列出同样多次)。列表的数量将由用户决定。我正在尝试找到一个O(n)效率的算法。
我一直在研究下面的代码,但是如果我不知道有多少个列表的话,我就不知道如何让它工作:

Integer[] a = {2, 2, 4, 6, 7, 11};
Integer[] b = {2, 2, 3, 5, 7, 14}
int i = 0;
int j = 0;
while(i < a.length && j < b.length) {
   if(a[i] == b[j]) {
      System.out.print(a[i] + " ");
      i++;
      j++;
   } else if(a[i] > b[j]) {
        j++;
   } else {
        i++;
   }
}

期望输出:二二七

5cnsuln7

5cnsuln71#

下面的代码是针对List而不是数组的,因为处理列表的动态数量稍微复杂一些,但是它支持所有ListCollectionIterable类型。
它适用于任何类型的Comparable值列表,例如IntegerLongDoubleStringDate ...
可以根据需要修改代码以处理Integer[]int[],或者任何其他数字基元类型,但是您必须克隆每种数组类型的代码。
未进行验证。列表必须预先排序,并且不允许为空。

@SafeVarargs
@SuppressWarnings("unchecked")
private static <E extends Comparable<E>> List<E> getCommonValues(Iterable<? extends E> ... lists) {
    // For each list: Get iterator and first value
    Iterator<? extends E>[] iter  = new Iterator[lists.length];
    E[] value = (E[])new Comparable[lists.length];
    for (int i = 0; i < lists.length; i++) {
        iter[i] = lists[i].iterator();
        value[i] = (iter[i].hasNext() ? iter[i].next() : null);
    }

    List<E> commonValues = new ArrayList<>();
    while (true) {

        // Find value count, lowest value, and count of lowest value
        int valueCount = 0, lowestCount = 0;
        E lowestValue = null;
        for (int i = 0; i < lists.length; i++)
            if (value[i] != null) {
                valueCount++;
                int cmp = (lowestValue == null ? -1 : value[i].compareTo(lowestValue));
                if (cmp < 0) {
                    lowestCount = 1;
                    lowestValue = value[i];
                } else if (cmp == 0) {
                    lowestCount++;
                }
            }

        // Exit loop if no more values
        if (valueCount == 0)
            break;

        // Save common value if all values were lowest value
        if (lowestCount == lists.length)
            commonValues.add(lowestValue);

        // For each list: Get next value if value was lowest value
        for (int i = 0; i < lists.length; i++)
            if (value[i] != null && value[i].compareTo(lowestValue) == 0)
                value[i] = (iter[i].hasNext() ? iter[i].next() : null);
    }

    return commonValues;
}
  • 测试 *
List<Integer> common = getCommonValues(Arrays.asList(2, 2, 4, 6, 7, 11),
                                       Arrays.asList(2, 2, 3, 5, 7, 14),
                                       Arrays.asList(2, 2, 2, 3, 3, 4, 5, 6, 7, 11, 14));
System.out.println(common);
  • 产出 *
[2, 2, 7]
hmae6n7t

hmae6n7t2#

我觉得这个有用,但我只在几个案子上用过。

public static void main(String[] args) {
    int[][] arrays = {{1, 1, 2, 2, 2, 3, 7, 7, 10, 10, 10}, 
                      {1, 1, 1, 2, 2, 3, 3, 7, 7, 7, 10}, 
                      {1, 1, 2, 2, 3, 7, 7, 10}};
    int n = arrays.length;
    int[] indices = new int[n];
    while (checkBounds(arrays, indices)) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++)
            max = Math.max(max, arrays[i][indices[i]]);
        boolean allEqualMax = true;
        for (int i = 0; i < n; i++) {
            if (arrays[i][indices[i]] < max) {
                indices[i]++;
                allEqualMax = false;
            }
        }
        if (allEqualMax) {
            System.out.print(max + " ");
            for (int i = 0; i < n; i++)
                indices[i]++;
        }
    }
}

private static boolean checkBounds(int[][] arrays, int[] indices) {
    for (int i = 0, n = arrays.length; i < n; i++)
        if (indices[i] >= arrays[i].length)
            return false;
    return true;
}
envsm3lx

envsm3lx3#

List接口提供了retainAll方法,该方法只保留所提供列表中源代码中的公共元素。

Integer[] a = { 2, 2, 4, 6, 7, 11 };
Integer[] b = { 2, 2, 3, 5, 7, 14 };

List<Integer> retained = new ArrayList<>(List.of(a));
retained.retainAll(List.of(b));
System.out.println(retained);

打印:[2,2,7]

相关问题