时间戳

首页 > 解决方案 > 如何找到 3 个数组中共有的最小数字？

java - 如何找到 3 个数组中共有的最小数字？

问题描述

这是问题：

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

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

谢谢您的帮助。

标签： javaarraylisttime-complexitycomplexity-theory

解决方案

稍微不同的方法：

  • 将最短的数组变成有序集合
  • 将另外两个数组变成普通集合
  • 迭代该排序集，并为每个条目检查其他两个集合是否包含它。

其他两个包含的第一个数字必须是最小的公共条目。这可以防止您查看重复的条目（这在此处真的无关紧要），并且还避免了对所有三个数组进行排序。

最后，对于这样的小例子，任何正确的解决方案都足够好。仅当您谈论具有数千甚至数百万条目的列表时，不同解决方案的潜在权衡才有意义。

推荐阅读