如何找到三个数组中共同的最小数字？

Question

这是问题:

Given 3 random arrays of integers, write a method to find the smallest number that is common among the 3 arrays. HINT: Sort first and just traverse first few elements until you reach the common number
  [-1,-2, 4,5,6,1,2,3,3,3,1,1,1]
  [54,6,7,8,1,3,5,1]
  [1,6,9,1,0,2,1]
  result = 1

我写了一个可行的解决方案，但我想知道是否有更简单和更高效的方法来完成这个任务。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;

public class Smcomm {

    public static void main(String[] args) {
        int[] A = {-1,-2,4,5,6,1,2,3,3,3,1,1,1};
        int[] B = {54,6,7,8,1,3,5,1};
        int[] C = {1,6,9,1,0,2,1};

        ArrayList<Integer> ar1 = new ArrayList<Integer>();
        ArrayList<Integer> ar2 = new ArrayList<Integer>();
        ArrayList<Integer> ar3 = new ArrayList<Integer>();

        for(int el: A){
            ar1.add(el);
        }

        for(int el: B){
            ar2.add(el);
        }

        for(int el: C){
            ar3.add(el);
        }

        Collections.sort(ar1);
        Collections.sort(ar2);
        Collections.sort(ar3);

        printer(ar1);
        printer(ar2);
        printer(ar3);

        finder(ar1,ar2,ar3);





    }


    static void printer(ArrayList ar){

        Iterator<Integer> it = ar.iterator();

        while(it.hasNext()){
            System.out.println(it.next());
        }
        System.out.println("--------------------");
    }

    static void finder(ArrayList ar1, ArrayList ar2, ArrayList ar3){
        ar1.retainAll(ar2);
        ar1.retainAll(ar3);
        if(ar1.size()>0){
            System.out.println(ar1.get(1));
        }else {
            System.out.println("no comm el");
        }
    }

}

我不太相信的方法是retainAll，因为我认为它的复杂度是O(n^2)。

我不需要找到所有的元素，只想找到最小的元素。您知道是否有可能在方法找到数组中第一个共同元素时停止方法的执行吗？这应该不难，因为数组已经排序过了。

感谢您的帮助。

- Andrea Mancini

---

如果您已经有一个可用的解决方案，但希望得到改进，那么您应该在Code Review上发布。 - Joakim Danielson

嗨@Andreamanchini，我刚刚发布了一个关于如何实现所提供的提示的答案：“首先排序，然后只需遍历前几个元素，直到达到公共数字”。 - Brother

Answer 1

稍微不同的方法：

• 将最短数组转换为排序集合
• 将另外两个数组转换为普通集合
• 遍历已排序的集合，并对于每个条目，检查其他两个集合是否包含它。

其他两个集合都包含的第一个数字必须是最小的公共条目。这样就可以避免查看重复条目（这里真的无关紧要），也避免了对三个数组进行排序。

最终，在这种小例子中，任何正确的解决方法都足够好。不同解决方案的潜在权衡只有在涉及具有数千，甚至数百万条目的列表时才有影响。

- GhostCat

Answer 2

首先，没有必要将数组转换为 List（因为您不需要使用 retainAll，它会查找3个数组的所有公共元素，这超出了您的需求）。

对数组（或列表）进行排序似乎是必要的，以确保最坏情况下的复杂度为O(NlogN)。我认为你不能做得比这更好。

一旦有了三个排序后的数组，就可以使用单个while循环和三个索引（每个数组一个）遍历三个数组，直到找到在三个数组中都出现的第一个元素。这将花费线性时间。

最后一件事 - 您当前的解决方案有一个小错误 - 它应该输出ar1.get(0)而不是ar1.get(1)。

- Eran

Answer 3

你可以只使用数组和foreach循环来简单地实现这个：

• 对数组进行排序
• 遍历数组A，并移动B和C，直到数字大于A。
• 检查它们是否相等，否则继续下一个数字，但避免再次通过相同的索引，从停止的位置继续。

这里是如何实现的示例：

public static void main(String[] args) {
    int[] A = {-1, -2, 4, 5, 6, 1, 2, 3, 3, 3, 1, 1, 1};
    int[] B = {54, 6, 7, 8, 1, 3, 5, 1};
    int[] C = {1, 6, 9, 1, 0, 2, 1};

    Arrays.sort(A);
    Arrays.sort(B);
    Arrays.sort(C);

    Optional<Integer> inCommon = findInCommon(A, B, C);

    if (inCommon.isPresent()) {
        System.out.println(inCommon.get());
    } else {
        System.out.println("no comm el");
    }
}

private static Optional<Integer> findInCommon(int[] A, int[] B, int[] C) {
    int lastB = 0;
    int lastC = 0;

    for (int valA : A) {
        while (B[lastB] < valA) lastB++;
        while (C[lastC] < valA) lastC++;

        if (valA == B[lastB] && valA == C[lastC]) {
            return Optional.of(valA);
        }
    }
    return Optional.empty();
}

- Brother

Answer 4

另一种使用Java 8流的方法，其中计算交集，然后找到最小值：

 List<Integer> list1 = Arrays.asList(A);
 List<Integer> list2 = Arrays.asList(B);
 List<Integer> list3 = Arrays.asList(C);

 Set<Integer> commonElements = list1.stream().filter(list2::contains).filter(list3::contains).collect(Collectors.toSet());
 int minimumCommonElement = Collections.min(commonElements);

- TechFree

---

提示：在使用contains之前，应首先对它们进行排序。否则可能会导致最差的性能表现。对于简单的数组来说，在我的观点中创建不必要的对象并不是一个好的性能表现。 - Brother

Answer 5

我认为最简单的方法是将元素存储在TreeSet中（它自然排序并删除重复项），而不是ArrayList，然后只需遍历集合1的每个元素，直到找到存在于所有3个集合中的元素。

static void finder(Set<Integer> s1, Set<Integer> s2, Set<Integer> s3) {
    boolean found=false;
    for (int i: s1) {
        if (s2.contains(i) && s3.contains(i)) {
            System.out.println(i);
            found=true;
            break;
        }
    }
    if (!found) {
        System.out.println("no comm el");
    }
}

- user27158

Answer 6

以下方法非常有效。我想到你只需要对其中一个列表进行排序，并将其用作迭代的源。

      List<Integer> list1 = new ArrayList<>(
      List.of(-1, -2, 4, 5, 6, 3, 1, 2, 3, 3, 3, 1, 1, 1));
      List<Integer> list2 = new ArrayList<>(List.of(54, 6, 7, 8, -4, 1, 3, 5, 1));
      List<Integer> list3 = new ArrayList<>(List.of(1, 6, 9, 1, 0, -4, 2, 1));

      Collections.sort(list1);
      for (int e : list1) {
         if (list2.contains(e) && list3.contains(e)) {
            System.out.println(e);
            break;
         }
      }

这里的想法是，如果e在list1（排序后的列表）中最小，那么如果它在list2和list3中，它必须是三个列表中共同的最小值。

使用集合去除重复项可能会带来一些改进。但是，除非数据最初就包含在集合中，否则也可能存在性能问题。

刚刚查看了其他答案，有人建议对最小的列表（或集合）进行排序。这是一个我没有考虑过的绝妙主意。

- WJS