如何找到三个数组中最常见的最小数？

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)。

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

谢谢你的帮助。

Answer 1

一种略有不同的办法：

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

其他两个项中包含的第一个数字必须是最小的公共项。这使您无法查看重复的条目(这在这里并不重要)，而且它也避免了对所有三个数组进行排序。

最后，对于这样的小例子，任何正确的解决方案都是足够好的。对于不同的解决方案，潜在的权衡只有在你谈论有成千上万甚至数百万条目的列表时才会起作用。

Answer 2

首先，不需要将数组转换为List(因为您不需要使用retainAll )。

为了确保O(NlogN)的最坏情况复杂性，对数组(或列表)进行排序似乎是必要的。我不相信你能做得更好。

一旦有了3个排序数组，就可以使用3个索引(每个数组一个索引)来遍历这3个数组，直到找到出现在所有3个数组中的第一个元素。这将需要线性时间。

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

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();
}