Как найти наименьшее число, которое является общим среди 3 массивов? - PullRequest
Новая
       31

Как найти наименьшее число, которое является общим среди 3 массивов?

2 голосов
/ 12 июня 2019

Это вопрос: 

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

Мне не нужно находить все элементыно я хочу найти только самых маленьких.Знаете ли вы, возможно, возможно ли каким-то образом остановить выполнение метода, когда он найдет первый общий элемент в массиве?Не должно быть трудным, потому что массивы уже отсортированы.

Спасибо за помощь.

Ответы [ 6 ]

3 голосов
/ 12 июня 2019

Немного другой подход:

  • превратить самый короткий массив в отсортированный набор
  • превратить два других массива в обычные наборы
  • итерируйте этот отсортированный набор, и для каждой записи проверьте, содержат ли другие два набора это.

Первое число, которое содержат оба других, должно быть наименьшей общей записью. Это предотвращает просмотр дублирующихся записей (которые на самом деле здесь не важны), а также позволяет избежать сортировки всех трех массивов.

В конце концов, для таких маленьких примеров достаточно правильного решения. Потенциальные компромиссы для разных решений имеют значение только тогда, когда речь идет о списках с тысячами и даже миллионами записей.

2 голосов
/ 12 июня 2019

Прежде всего, нет необходимости преобразовывать массивы в List s (поскольку вам не нужно использовать retainAll, который находит все общие элементы из 3-х массивов, что больше, чем нужно).

Сортировка массивов (или списков) представляется необходимой для обеспечения сложности наихудшего случая O (NlogN). Я не верю, что ты можешь добиться большего, чем это.

Если у вас есть 3 отсортированных массива, вы можете перебирать 3 массива с помощью одного цикла while, используя 3 индекса (по одному для каждого массива), пока не найдете первый элемент, который появляется во всех 3 массивах. Это займет линейное время.

И последнее: ваше текущее решение содержит небольшую ошибку - оно должно вывести ar1.get(0), а не ar1.get(1).

0 голосов
/ 12 июня 2019

Следующее работает довольно хорошо. Мне пришло в голову, что вам нужно только отсортировать один из списков и использовать его в качестве источника для взаимодействия. 

      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, оно должно быть наименьшим общим для всех трех.

Можно добиться некоторого улучшения, удалив дубликаты с помощью наборов. Но с этим тоже могут быть проблемы с производительностью, если только данные изначально не содержались в наборах для запуска.

Просто просмотрев другие ответы, кто-то предложил отсортировать наименьший список (или набор). Это отличная идея, которую я не рассматривал.

0 голосов
/ 12 июня 2019

Я думаю, что самый простой способ добиться этого - хранить ваши элементы в 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");
    }
}
0 голосов
/ 12 июня 2019

Другой подход, использующий потоки 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);
0 голосов
/ 12 июня 2019

Вы можете использовать только Arrays и цикл 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();
}
...