3
long[] a = new long[]{45017,96741,11751,23772,58825};
long[] b = new long[]{23772,88781,23777};

Как 2 массива объединить в один, чтобы в новом (третьем) массиве были только совпадающие элементы, в данном случае 23772 ?

7
  • а вам с какой сложностью решение надо? В лоб за O(nm) поумнее за O(n log m) или за O(n+m)?
    – pavel
    13 окт 2015 в 20:29
  • @pavel интересно про О(n+m). Можно ссылку, где почитать? Спасибо 13 окт 2015 в 20:33
  • для получения O(n+m) есть смысл воспользоваться multiset или map, теми которые hash. Алгоритм - ложим в hash multiset весь массив а, потом идём по массиву b, если элемент есть в сете, то удаляем его и ложим в массив - ответ.
    – pavel
    13 окт 2015 в 20:40
  • @pavel - а поиск по hash multiset за константное время? О_о... вот я раньше мучился( 13 окт 2015 в 20:42
  • можно конкретные примеры?
    – dll
    13 окт 2015 в 20:50

4 ответа 4

4

На Java-8:

long[] result = LongStream.concat(Arrays.stream(a), Arrays.stream(b)).distinct().toArray();
1

Как вариант:

private static List<Long> asList(long[] array) {
    List<Long> res = new ArrayList<>(array.length);
    for (long l : array) {
        res.add(l);
    }
    return res;
}

public static void main(String[] args) {
    long[] a = new long[]{45017,96741,11751,23772,58825};
    long[] b = new long[]{23772,88781,23777};
    List<Long> cList = asList(a);
    cList.retainAll(asList(b));

    System.out.println(cList);
}
1

Вот решение с временной сложностью O(m + n):

private static Long[] getIntersection (long[] a, long[] b) {
    HashSet<Long> aSet = new HashSet<>(),
        bSet = new HashSet<>();
    for(int i = 0; i < a.length; i++) {
        aSet.add(a[i]);
    }
    for(int i = 0; i < b.length; i++) {
        bSet.add(b[i]);
    }
    ArrayList<Long> intersection = new ArrayList<>();
    for(Long l : aSet) {
        if(bSet.contains(l)) {
            intersection.add(l);
        }
    }
    return intersection.toArray(new Long[]{});
}
0
  1. В верхнем цикле пробегайтесь по элементам 1-го массива
  2. Во внутреннем цикле сравнивайте элемент 1-го массива со всеми элементами второго до тех пор пока не будет совпадения.
  3. При совпадении помещайте совпавший элемент в список.
  4. Список преобразуйте в массив.
2
  • Немного не точно сформулировал вопрос, а если неизвестное количество входных массивов, как получить?
    – dll
    13 окт 2015 в 20:48
  • Добавьте ещё один вложенный цикл, который будет все массивы перебирать. Если надо при этом, чтобы искомое значение присутствовало во всех массивах, то просто завершайте цикл при ненахождении значения первого массива в любом из остальных.
    – ЮрийСПб
    13 окт 2015 в 20:52

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.