Как объединить два отсортированных массива в отсортированный массив? [закрыто]

160

Об этом меня спросили в интервью, и вот решение, которое я предоставил:

public static int[] merge(int[] a, int[] b) {

    int[] answer = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;
    while (i < a.length && j < b.length)
    {
        if (a[i] < b[j])
        {
            answer[k] = a[i];
            i++;
        }
        else
        {
            answer[k] = b[j];
            j++;
        }
        k++;
    }

    while (i < a.length)
    {
        answer[k] = a[i];
        i++;
        k++;
    }

    while (j < b.length)
    {
        answer[k] = b[j];
        j++;
        k++;
    }

    return answer;
}

Есть ли более эффективный способ сделать это?

Изменить: Исправлены методы длины.

Behrooz Karjoo
источник
30
Похоже, довольно хороший ответ для меня. Эта проблема в лучшем случае будет иметь сложность O (n), и ваш ответ достигает этого. Все остальное будет микрооптимизацией.
Дрю Холл
3
Ты хорошо справился! По сути, это является частью сортировки слиянием: объединение двух отсортированных потоков (с ленты или диска) в другой отсортированный поток.
Владимир Дюжев
9
У тебя есть работа?
Шай
5
Также вы можете использовать троичный оператор: while (i < a.length && j < b.length) answer[k++] = a[i] < b[j] ? a[i++] : b[j++]; Java Спецификация языка: Условный оператор? : .
Антон Дозорцев
1
Вы забыли прокомментировать !!!
LiziPizi

Ответы:

33

Незначительное улучшение, но после основного цикла вы можете использовать System.arraycopyдля копирования хвоста любого входного массива, когда доберетесь до конца другого. Это не изменит O(n)характеристики производительности вашего решения.

Грег Хьюгилл
источник
109
public static int[] merge(int[] a, int[] b) {

    int[] answer = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;

    while (i < a.length && j < b.length)  
       answer[k++] = a[i] < b[j] ? a[i++] :  b[j++];

    while (i < a.length)  
        answer[k++] = a[i++];

    while (j < b.length)    
        answer[k++] = b[j++];

    return answer;
}

Это немного более компактно, но точно так же!

Майк Саулл
источник
Человеку, который сказал, что это вызвало исключение индекса за пределами границ, какие входные данные вы используете? Это работает во всех случаях для меня.
Майк Саулл
1
Используйте цикл for для объединения строк, объявляющих переменные цикла и управление циклом. Используйте двойные пустые строки экономно - выглядит неуместно между симметричными "копиями хвоста".
седобородый
58

Я удивлен, что никто не упомянул эту гораздо более классную, эффективную и компактную реализацию:

public static int[] merge(int[] a, int[] b) {
    int[] answer = new int[a.length + b.length];
    int i = a.length - 1, j = b.length - 1, k = answer.length;

    while (k > 0)
        answer[--k] =
                (j < 0 || (i >= 0 && a[i] >= b[j])) ? a[i--] : b[j--];
    return answer;
}

Точки интересов

  1. Обратите внимание, что он выполняет то же или меньшее количество операций, что и любой другой алгоритм O (n) , но буквально в одном выражении в одном цикле while!
  2. Если два массива имеют приблизительно одинаковый размер, то постоянная для O (n) одинакова. Однако, если массивы действительно несбалансированы, то версии с System.arraycopyвыиграют, потому что внутренне это можно сделать с помощью одной инструкции сборки x86.
  3. Обратите внимание, a[i] >= b[j]вместо a[i] > b[j]. Это гарантирует «стабильность», которая определяется, когда элементы a и b равны, нам нужны элементы от a до b.
Шиталь шах
источник
Это действительно очень хороший подход. У меня были проблемы с получением хороших тестов для моих алгоритмов сортировки слиянием в Swift lang. Преобразование этого дало мне то, что мне было нужно, большое спасибо
Chackle
Какова точка (j <0) в цикле while? Кстати, +1, это действительно круто! Спасибо, что поделился.
Hengameh
2
@Hengameh в случае j < 0, bуже исчерпан, поэтому мы продолжаем добавлять оставшиеся aэлементы в answer массив
Натан Streppel
6
Слишком "умный" и трудно читать в моей голове. Я предпочитаю более легкий для чтения код, тем более что вы не достигли значительного улучшения производительности с помощью этого кода.
Кевин М
1
плюс за Уведомление и a [i]> = b [j] вместо a [i]> b [j]. Это гарантирует «стабильность»
Ян Хонски
16

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

ChrisH
источник
Если a велико, а b мало, то этот алгоритм неверен.
Джек,
7
Это не так, но не эффективно.
Джек,
@ Джек, как вы можете сделать это быстрее, чем O (n), когда вы производите массив из n элементов?
Будет
@will System.arrayCopy()тупо быстр, поскольку использует memcpyвызовы, оптимизированные для процессора . Так что есть возможность улучшить производительность путем копирования фрагментов. Также есть возможность бинарного поиска границ.
тонкая
Особенно, если вы можете использовать отсортированную природу, чтобы пропустить большинство записей и никогда не сравнивать их. Вы действительно можете победить O (n).
Tatarize
10

Это решение также очень похоже на другие публикации, за исключением того, что оно использует System.arrayCopy для копирования оставшихся элементов массива.

private static int[] sortedArrayMerge(int a[], int b[]) {
    int result[] = new int[a.length +b.length];
    int i =0; int j = 0;int k = 0;
    while(i<a.length && j <b.length) {
        if(a[i]<b[j]) {
            result[k++] = a[i];
            i++;
        } else {
            result[k++] = b[j];
            j++;
        }
    }
    System.arraycopy(a, i, result, k, (a.length -i));
    System.arraycopy(b, j, result, k, (b.length -j));
    return result;
}
Пани Дхакшнамурти
источник
7

Вот обновленная функция. Он удаляет дубликаты, надеюсь, кто-то найдет это пригодным для использования:

public static long[] merge2SortedAndRemoveDublicates(long[] a, long[] b) {
    long[] answer = new long[a.length + b.length];
    int i = 0, j = 0, k = 0;
    long tmp;
    while (i < a.length && j < b.length) {
        tmp = a[i] < b[j] ? a[i++] : b[j++];
        for ( ; i < a.length && a[i] == tmp; i++);
        for ( ; j < b.length && b[j] == tmp; j++);
        answer[k++] = tmp;
    }
    while (i < a.length) {
        tmp = a[i++];
        for ( ; i < a.length && a[i] == tmp; i++);
        answer[k++] = tmp;
    }
    while (j < b.length) {
        tmp = b[j++];
        for ( ; j < b.length && b[j] == tmp; j++);
        answer[k++] = tmp;
    }
    return Arrays.copyOf(answer, k);
}
vitali_y
источник
+1, спасибо, что поделились. Один вопрос: почему вы выбрали тип массива и тип переменной 'temp', long?
Hengameh
(У меня есть сомнения по поводу названия метода.)
Greybeard
5

Это можно сделать в 4 заявления, как показано ниже

 int a[] = {10, 20, 30};
 int b[]= {9, 14, 11};
 int res[]=new int[a.legth+b.length]; 
 System.arraycopy(a,0, res, 0, a.length); 
 System.arraycopy(b,0,res,a.length, b.length);
 Array.sort(res)

Судир
источник
5
Я не понимаю, почему этот ответ получил отрицательные голоса. Это правда, что это не эффективно. Но иногда все, что вам нужно, это сделать работу как можно скорее. Если вы имеете дело с очень маленькими массивами, скажем, менее 100 элементов, я бы предпочел использовать приведенный выше код, а не писать длинный код, который не принесет существенных улучшений производительности. Итак, спасибо Sudhir за предоставление этого простого решения и SANN3 за его редактирование.
Ахмедов
2
Неписанная предпосылка заключается в том, что sortфункция не может использовать себя в качестве метода сортировки. Это было бы бесконечной регрессией вместо рекурсии. Также другая предпосылка заключается в том, что merge_array - это функция, которая реализует сортировку. Таким образом, этот ответ непригоден в наиболее вероятном контексте.
Аки Суйхконен
Заданный вопрос не упоминал, что требуемый код был только для небольшого массива. Так что этот ответ будет вводить в заблуждение, если в нем четко не указано его ограничение. Также посмотрите на мой ответ ниже. Требуется такое же количество строк, чтобы написать эффективный код, который работает для любого размера массива :)
Shital Shah
Вопрос предусматривал, что массивы уже в отсортированном порядке. Если бы массивы могли быть очень большими, это решение остановилось бы и работало плохо. Поэтому убедитесь, что вы получите требуемые конечные результаты, но приложение не будет работать, и вы не получите работу, если бы я брал интервью.
Кевин М
Функция Array.sort () использует TimSort, который очень найдет отсортированные прогоны и применяет сортировку слиянием к ним. Как ни странно, этот код не может быть даже ошибочным из-за «неэффективности», поскольку он фактически завершится за O (n) из-за отсортированных запусков. Вы можете выполнить кучу тестов на это, шансы хороши, что он будет побеждать OP-код довольно часто.
Tatarize
4

Я должен был написать это в JavaScript, вот оно:

function merge(a, b) {
    var result = [];
    var ai = 0;
    var bi = 0;
    while (true) {
        if ( ai < a.length && bi < b.length) {
            if (a[ai] < b[bi]) {
                result.push(a[ai]);
                ai++;
            } else if (a[ai] > b[bi]) {
                result.push(b[bi]);
                bi++;
            } else {
                result.push(a[ai]);
                result.push(b[bi]);
                ai++;
                bi++;
            }
        } else if (ai < a.length) {
            result.push.apply(result, a.slice(ai, a.length));
            break;
        } else if (bi < b.length) {
            result.push.apply(result, b.slice(bi, b.length));
            break;
        } else {
            break;
        }
    }
    return result;
}
ebdr
источник
4

Apache collection поддерживает метод сортировки начиная с версии 4; Вы можете сделать это, используя collateметод в:

org.apache.commons.collections4.CollectionUtils

Вот цитата из Javadoc:

collate(Iterable<? extends O> a, Iterable<? extends O> b, Comparator<? super O> c)

Объединяет две отсортированные коллекции aи bв один отсортированный список таким образом, что порядок элементов согласно Comparator c сохраняется.

Не изобретай велосипед! Ссылка на документ: http://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/CollectionUtils.html

Влад
источник
4

GallopSearch Merge: O (log (n) * log (i)), а не O (n)

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

  • Код использует gallopSearch, который равен O (log (i)), где i - это расстояние от текущего индекса, для которого существует соответствующий индекс.
  • В коде используется двоичный поиск после того, как поиск галопом определил правильный диапазон. Поскольку галоп ограничил это меньшим диапазоном, получаемый двоичный поиск также равен O (log (i))
  • Галоп и слияние выполняются задом наперед. Это не кажется критически важным, но позволяет объединять массивы. Если один из ваших массивов имеют достаточно мест для хранения значений результатов, вы можете просто использовать его в качестве присоединяемого массива и массива результатов. В этом случае вы должны указать допустимый диапазон в массиве.
  • В этом случае не требуется выделение памяти (большая экономия при критических операциях). Он просто проверяет, не перезаписывает ли необработанные значения (что может быть сделано только в обратном направлении). Фактически вы используете один и тот же массив как для входных данных, так и для результатов. Он не будет страдать от вредных последствий
  • Я последовательно использовал Integer.compare (), чтобы это можно было отключить для других целей.
  • Есть некоторый шанс, что я мог бы немного обмануть и не использовать информацию, которую я ранее доказал. Например, двоичный поиск в диапазоне двух значений, для которого уже проверено одно значение. Также мог бы быть лучший способ сформулировать основной цикл, если бы значение c flipping c не потребовалось бы, если бы они были последовательно объединены в две операции. Поскольку вы знаете, что будете делать одно, то другое каждый раз. Есть место для полировки.

Это должен быть наиболее эффективный способ сделать это с временной сложностью O (log (n) * log (i)), а не O (n). И в худшем случае временная сложность O (n). Если ваши массивы клочковатые и содержат длинные цепочки значений, это затмит любой другой способ сделать это, иначе это будет просто лучше, чем они.

Он имеет два значения чтения на концах массива объединения и значение записи в массиве результатов. После того, как выясняется, какое из конечных значений меньше, он делает скачок в этом массиве. 1, 2, 4, 8, 16, 32 и т. Д. Когда он находит диапазон, в котором значение чтения другого массива больше. Он выполняет двоичный поиск в этом диапазоне (сокращает диапазон пополам, ищет правильную половину, повторяет до одного значения). Затем массив копирует эти значения в позицию записи. Помните, что копия по необходимости перемещается так, что не может перезаписывать одинаковые значения из любого массива чтения (что означает, что массив записи и массив чтения могут быть одинаковыми). Затем он выполняет ту же операцию для другого массива, который, как теперь известно, меньше нового значения чтения другого массива.

static public int gallopSearch(int current, int[] array, int v) {
    int d = 1;
    int seek = current - d;
    int prevIteration = seek;
    while (seek > 0) {
        if (Integer.compare(array[seek], v) <= 0) {
            break;
        }
        prevIteration = seek;
        d <<= 1;
        seek = current - d;
        if (seek < 0) {
            seek = 0;
        }
    }
    if (prevIteration != seek) {
        seek = binarySearch(array, seek, prevIteration, v);
        seek = seek >= 0 ? seek : ~seek;
    }
    return seek;
}

static public int binarySearch(int[] list, int fromIndex, int toIndex, int v) {
    int low = fromIndex;
    int high = toIndex - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = list[mid];
        int cmp = Integer.compare(midVal, v);
        if (cmp < 0) {
            low = mid + 1;
        } else if (cmp > 0) {
            high = mid - 1;
        } else {
            return mid;// key found
        }
    }
    return -(low + 1);// key not found.
}

static public int[] sortedArrayMerge(int[] a, int[] b) {
    return sortedArrayMerge(null, a, a.length, b, b.length);
}

static public int[] sortedArrayMerge(int[] results, int[] a, int aRead, int b[], int bRead) {
    int write = aRead + bRead, length, gallopPos;
    if ((results == null) || (results.length < write)) {
        results = new int[write];
    }
    if (aRead > 0 && bRead > 0) {
        int c = Integer.compare(a[aRead - 1], b[bRead - 1]);
        while (aRead > 0 && bRead > 0) {
            switch (c) {
                default:
                    gallopPos = gallopSearch(aRead, a, b[bRead-1]);
                    length = (aRead - gallopPos);
                    write -= length;
                    aRead = gallopPos;
                    System.arraycopy(a, gallopPos--, results, write, length);
                    c = -1;
                    break;
                case -1:
                    gallopPos = gallopSearch(bRead, b, a[aRead-1]);
                    length = (bRead - gallopPos);
                    write -= length;
                    bRead = gallopPos;
                    System.arraycopy(b, gallopPos--, results, write, length);
                    c = 1;
                    break;
            }
        }
    }
    if (bRead > 0) {
        if (b != results) {
            System.arraycopy(b, 0, results, 0, bRead);
        }
    } else if (aRead > 0) {
        if (a != results) {
            System.arraycopy(a, 0, results, 0, aRead);
        }
    }
    return results;
}

Это должен быть самый эффективный способ сделать это.


У некоторых ответов была возможность удаления дубликатов. Это потребует алгоритма O (n), потому что вы должны сравнить каждый элемент. Так что вот для этого отдельная вещь, которая будет применяться после факта. Вы не можете просматривать несколько записей, если вам нужно просмотреть все из них, хотя вы могли бы просматривать дубликаты, если их было много.

static public int removeDuplicates(int[] list, int size) {
    int write = 1;
    for (int read = 1; read < size; read++) {
        if (list[read] == list[read - 1]) {
            continue;
        }
        list[write++] = list[read];
    }
    return write;
}

Обновление: предыдущий ответ, не ужасный код, но явно уступает вышеуказанному.

Еще одна ненужная гипероптимизация. Он не только запускает arraycopy для конечных битов, но и для начала. Обработка любого вводного непересекающегося в O (log (n)) двоичного поиска в данных. O (log (n) + n) - это O (n), и в некоторых случаях эффект будет довольно выраженным, особенно в тех случаях, когда вообще нет перекрытия между объединяющимися массивами.

private static int binarySearch(int[] array, int low, int high, int v) {
    high = high - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = array[mid];
        if (midVal > v)
            low = mid + 1;
        else if (midVal < v)
            high = mid - 1;
        else
            return mid; // key found
    }
    return low;//traditionally, -(low + 1);  // key not found.
}

private static int[] sortedArrayMerge(int a[], int b[]) {
    int result[] = new int[a.length + b.length];
    int k, i = 0, j = 0;
    if (a[0] > b[0]) {
        k = i = binarySearch(b, 0, b.length, a[0]);
        System.arraycopy(b, 0, result, 0, i);
    } else {
        k = j = binarySearch(a, 0, a.length, b[0]);
        System.arraycopy(a, 0, result, 0, j);
    }
    while (i < a.length && j < b.length) {
        result[k++] = (a[i] < b[j]) ? a[i++] : b[j++];
    }
    if (j < b.length) {
        System.arraycopy(b, j, result, k, (b.length - j));
    } else {
        System.arraycopy(a, i, result, k, (a.length - i));
    }
    return result;
}
Tatarize
источник
1
Проголосовал за то, что начал что-то делать с симметрией, но зачем останавливаться на достигнутом? Используйте скачущий поиск, чтобы он возвращал индекс после равных ключей. Используйте копию массива, если более 3 элементов, только. Обратите внимание, что после этой копии ничего не изменилось, кроме: а) начального индекса в одном входном и выходном массиве; б) вашего знания о том, какой «следующий» элемент меньше.
седобородый
Это то, что делает реализованный Arrays.sort. Это, в худшем случае, слияние. Я думаю, что они меняют 2 элемента, где это необходимо, но попадают в arraycopy для более чем 2 элементов. Я не уверен относительно того, будете ли вы проверять следующий элемент линейно или выполнять бинарный поиск в нем. Было бы довольно большим преимуществом спекулятивно проверять, можете ли вы прыгнуть на большее расстояние, если бы вы могли прыгнуть на это расстояние. Как и в случае с проверкой 8, и если вы можете скопировать это, вы сэкономили 7 операций, которые вам не нужны.
Tatarize
@greybeard ... и готово. Также пошел назад, чтобы я мог использовать ту же память.
Tatarize
Хорошо, что ты мотивировал баллистику. Собираюсь присмотреться после дневных поглотителей времени.
седобородый
That is totally what the implemented Arrays.sort does( То есть : из первой редакции вашего ответа - или - из моего комментария 19 февраля?) - вы не можете найти ни в SunDK JDK 8: на какую реализацию Arrays.sortвы ссылаетесь?
седобородый
2

Вот сокращенная форма, написанная на javascript:

function sort( a1, a2 ) {

    var i = 0
        , j = 0
        , l1 = a1.length
        , l2 = a2.length
        , a = [];

    while( i < l1 && j < l2 ) {

        a1[i] < a2[j] ? (a.push(a1[i]), i++) : (a.push( a2[j]), j++);
    }

    i < l1 && ( a = a.concat( a1.splice(i) ));
    j < l2 && ( a = a.concat( a2.splice(j) ));

    return a;
}
swallace
источник
1
    public class Merge {

    // stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi]
    public static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {

        // precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
        assert isSorted(a, lo, mid);
        assert isSorted(a, mid+1, hi);

        // copy to aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k]; 
        }

        // merge back to a[]
        int i = lo, j = mid+1;
        for (int k = lo; k <= hi; k++) {
            if      (i > mid)              a[k] = aux[j++];
            else if (j > hi)               a[k] = aux[i++];
            else if (less(aux[j], aux[i])) a[k] = aux[j++];
            else                           a[k] = aux[i++];
        }

        // postcondition: a[lo .. hi] is sorted
        assert isSorted(a, lo, hi);
    }

    // mergesort a[lo..hi] using auxiliary array aux[lo..hi]
    private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }

    public static void sort(Comparable[] a) {
        Comparable[] aux = new Comparable[a.length];
        sort(a, aux, 0, a.length-1);
        assert isSorted(a);
    }


   /***********************************************************************
    *  Helper sorting functions
    ***********************************************************************/

    // is v < w ?
    private static boolean less(Comparable v, Comparable w) {
        return (v.compareTo(w) < 0);
    }

    // exchange a[i] and a[j]
    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }


   /***********************************************************************
    *  Check if array is sorted - useful for debugging
    ***********************************************************************/
    private static boolean isSorted(Comparable[] a) {
        return isSorted(a, 0, a.length - 1);
    }

    private static boolean isSorted(Comparable[] a, int lo, int hi) {
        for (int i = lo + 1; i <= hi; i++)
            if (less(a[i], a[i-1])) return false;
        return true;
    }


   /***********************************************************************
    *  Index mergesort
    ***********************************************************************/
    // stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi]
    private static void merge(Comparable[] a, int[] index, int[] aux, int lo, int mid, int hi) {

        // copy to aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = index[k]; 
        }

        // merge back to a[]
        int i = lo, j = mid+1;
        for (int k = lo; k <= hi; k++) {
            if      (i > mid)                    index[k] = aux[j++];
            else if (j > hi)                     index[k] = aux[i++];
            else if (less(a[aux[j]], a[aux[i]])) index[k] = aux[j++];
            else                                 index[k] = aux[i++];
        }
    }

    // return a permutation that gives the elements in a[] in ascending order
    // do not change the original array a[]
    public static int[] indexSort(Comparable[] a) {
        int N = a.length;
        int[] index = new int[N];
        for (int i = 0; i < N; i++)
            index[i] = i;

        int[] aux = new int[N];
        sort(a, index, aux, 0, N-1);
        return index;
    }

    // mergesort a[lo..hi] using auxiliary array aux[lo..hi]
    private static void sort(Comparable[] a, int[] index, int[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, index, aux, lo, mid);
        sort(a, index, aux, mid + 1, hi);
        merge(a, index, aux, lo, mid, hi);
    }

    // print array to standard output
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            StdOut.println(a[i]);
        }
    }

    // Read strings from standard input, sort them, and print.
    public static void main(String[] args) {
        String[] a = StdIn.readStrings();
        Merge.sort(a);
        show(a);
    }
}
jackhao
источник
Что это скопировать a[mid+1 .. hi]в auxтечение?
седобородый
1

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

sriragav
источник
1
public int[] merge(int[] a, int[] b) {
    int[] result = new int[a.length + b.length];
    int aIndex, bIndex = 0;

    for (int i = 0; i < result.length; i++) {
        if (aIndex < a.length && bIndex < b.length) {
            if (a[aIndex] < b[bIndex]) {
                result[i] = a[aIndex];
                aIndex++;
            } else {
                result[i] = b[bIndex];
                bIndex++;
            }
        } else if (aIndex < a.length) {
            result[i] = a[aIndex];
            aIndex++;
        } else {
            result[i] = b[bIndex];
            bIndex++;
        }
    }

    return result;
}
Андрей
источник
2
Некоторое объяснение было бы неплохо. :)
gsamaras
1
public static int[] merge(int[] a, int[] b) {
    int[] mergedArray = new int[(a.length + b.length)];
    int i = 0, j = 0;
    int mergedArrayIndex = 0;
    for (; i < a.length || j < b.length;) {
        if (i < a.length && j < b.length) {
            if (a[i] < b[j]) {
                mergedArray[mergedArrayIndex] = a[i];
                i++;
            } else {
                mergedArray[mergedArrayIndex] = b[j];
                j++;
            }
        } else if (i < a.length) {
            mergedArray[mergedArrayIndex] = a[i];
            i++;
        } else if (j < b.length) {
            mergedArray[mergedArrayIndex] = b[j];
            j++;
        }
        mergedArrayIndex++;
    }
    return mergedArray;
}
toobsco42
источник
Какова спасительная грация этого? Это может быть сокращено до for (int i, j, k = i = j = 0 ; k < c.length ; ) c[k++] = b.length <= j || i < a.length && a[i] < b[j] ? a[i++] : b[j++];. Чем он отличается от ответа Эндрю 2014 года ?
седобородый
1

Алгоритм может быть улучшен многими способами. Например, разумно проверить, если a[m-1]<b[0]или b[n-1]<a[0]. В любом из этих случаев нет необходимости делать больше сравнений. Алгоритм может просто скопировать исходные массивы в полученный в правильном порядке.

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

Хенгейм
источник
Для этого улучшения было бы лучше проверить, куда первый элемент попадет во второй массив, с помощью двоичного поиска, а затем скопировать эти данные, чтобы начать. Тогда в случае, если одна из этих проверок верна, она просто скопирует все массивы, затем скопирует троичную массив, и вы получите тот же результат. Но, в случае незначительного перекрытия, вам нужно только сделать правильный алгоритм во время перекрытия, а не в другое время. Поскольку вы застряли с O (n), с помощью какой-то быстрой команды O (logn) заранее ничего не будет стоить.
Tatarize
1

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

Я написал это на Python, но он также должен хорошо переводиться на Java:

def func(a, b):
    class sentinel(object):
        def __lt__(*_):
            return False

    ax, bx, c = a[:] + [sentinel()], b[:] + [sentinel()], []
    i, j = 0, 0

    for k in range(len(a) + len(b)):
        if ax[i] < bx[j]:
            c.append(ax[i])
            i += 1
        else:
            c.append(bx[j])
            j += 1

    return c
d11wtq
источник
массовое копирование элементов, чтобы (умело) использовать дозорного…
greybeard
1

Вы можете использовать 2 потока для заполнения результирующего массива, один спереди, один сзади.

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

tkruse
источник
0
//How to merge two sorted arrays into a sorted array without duplicates?
//simple C Coding
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

main()
{
    int InputArray1[] ={1,4,5,7,8,9,12,13,14,17,40};
    int InputArray2[] ={4,5,11,14,15,17,18,19,112,122,122,122,122};
    int n=10;
    int OutputArray[30];
    int i=0,j=0,k=0;
    //k=OutputArray
    while(i<11 && j<13)
    {
        if(InputArray1[i]<InputArray2[j])
        {
            if (k == 0 || InputArray1[i]!= OutputArray[k-1])
            {
                OutputArray[k++] = InputArray1[i];
            }
            i=i+1;
        }
        else if(InputArray1[i]>InputArray2[j])
        {
            if (k == 0 || InputArray2[j]!= OutputArray[k-1])
            {
                OutputArray[k++] = InputArray2[j];
            }
            j=j+1;
        }
        else
        {
            if (k == 0 || InputArray1[i]!= OutputArray[k-1])
            {
                OutputArray[k++] = InputArray1[i];
            }
            i=i+1;
            j=j+1;
        }
    };
    while(i<11)
    {
        if(InputArray1[i]!= OutputArray[k-1])
            OutputArray[k++] = InputArray1[i++];
        else
            i++;
    }
    while(j<13)
    {
        if(InputArray2[j]!= OutputArray[k-1])
            OutputArray[k++] = InputArray2[j++];
        else
            j++;
    }
    for(i=0; i<k; i++)
    {
        printf("sorted data:%d\n",OutputArray[i]);
    };
}
Chanchal
источник
0
public static int[] merge(int[] listA, int[] listB) {
        int[] mergedList = new int[ listA.length + listB.length];
        int i = 0; // Counter for listA
        int j = 0; // Counter for listB
        int k = 0; // Counter for mergedList
        while (true) {
            if (i >= listA.length && j >= listB.length) {
                break;
            }
            if (i < listA.length && j < listB.length) { // If both counters are valid.
                if (listA[i] <= listB[j]) {
                    mergedList[k] = listA[i];
                    k++;
                    i++;
                } else {
                    mergedList[k] = listB[j];
                    k++;
                    j++;
                }
            } else if (i < listA.length && j >= listB.length) { // If only A's counter is valid.
                mergedList[k] = listA[i];
                k++;
                i++;
            } else if (i <= listA.length && j < listB.length) { // If only B's counter is valid
                mergedList[k] = listB[j];
                k++;
                j++;
            }
        }
        return mergedList;
    }
Шон Вулфолк
источник
0
var arrCombo = function(arr1, arr2){
  return arr1.concat(arr2).sort(function(x, y) {
    return x - y;
  });
};
Алекс Хокинс
источник
2
Этот ответ не относится к языку программирования Java, хотя он был бы хорошим ответом для javascript.
gknicker
Это было частью собеседования. В этих случаях вы не должны писать «нормальный» код, как описано выше. Они ищут «эффективный» код и демонстрацию того, что вы понимаете используемые алгоритмы.
d11wtq 25.09.15
0

Мой любимый язык программирования - JavaScript

function mergeSortedArrays(a, b){
    var result = [];

    var sI = 0;
    var lI = 0;
    var smallArr;
    var largeArr;
    var temp;

    if(typeof b[0] === 'undefined' || a[0]<b[0]){
        smallArr = a;
        largeArr = b;
    } else{
        smallArr = b;
        largeArr = a;
    }

    while(typeof smallArr[sI] !== 'undefined'){
        result.push(smallArr[sI]);
        sI++;

        if(smallArr[sI]>largeArr[lI] || typeof smallArr[sI] === 'undefined'){
            temp = smallArr;
            smallArr = largeArr;
            largeArr = temp;
            temp = sI;
            sI = lI;
            lI = temp;
        }
    }
    return result;
}
Саад Ахмед
источник
0

Может быть, использовать System.arraycopy

public static byte[] merge(byte[] first, byte[] second){
    int len = first.length + second.length;
    byte[] full = new byte[len];
    System.arraycopy(first, 0, full, 0, first.length);
    System.arraycopy(second, 0, full, first.length, second.length);
    return full;
}
nurisezgin
источник
3
Вы просто объединяете их; Ваш результирующий массив сам не отсортирован, что было требованием.
Санджив Дхиман
0
public static void main(String[] args) {
    int[] arr1 = {2,4,6,8,10,999};
    int[] arr2 = {1,3,5,9,100,1001};

    int[] arr3 = new int[arr1.length + arr2.length];

    int temp = 0;

    for (int i = 0; i < (arr3.length); i++) {
        if(temp == arr2.length){
            arr3[i] = arr1[i-temp];
        }
        else if (((i-temp)<(arr1.length)) && (arr1[i-temp] < arr2[temp])){
                arr3[i] = arr1[i-temp];
        }
        else{
            arr3[i] = arr2[temp];
            temp++;
        }
    }

    for (int i : arr3) {
        System.out.print(i + ", ");
    }
}

Выход:

1, 2, 3, 4, 5, 6, 8, 9, 10, 100, 999, 1001,

Раджеш Гурбани
источник
Запутанно для именования индекса в arr2нет ind2, но temp.
седобородый
0

Вы можете использовать троичные операторы, чтобы сделать код немного более компактным

public static int[] mergeArrays(int[] a1, int[] a2) {
    int[] res = new int[a1.length + a2.length];
    int i = 0, j = 0;

    while (i < a1.length && j < a2.length) {
        res[i + j] = a1[i] < a2[j] ? a1[i++] : a2[j++];
    }

    while (i < a1.length) {
        res[i + j] = a1[i++];
    }

    while (j < a2.length) {
        res[i + j] = a2[j++];
    }

    return res;
}
Дженна Квон
источник
0
public static int[] mergeSorted(int[] left, int[] right) {
    System.out.println("merging " + Arrays.toString(left) + " and " + Arrays.toString(right));
    int[] merged = new int[left.length + right.length];
    int nextIndexLeft = 0;
    int nextIndexRight = 0;
    for (int i = 0; i < merged.length; i++) {
        if (nextIndexLeft >= left.length) {
            System.arraycopy(right, nextIndexRight, merged, i, right.length - nextIndexRight);
            break;
        }
        if (nextIndexRight >= right.length) {
            System.arraycopy(left, nextIndexLeft, merged, i, left.length - nextIndexLeft);
            break;
        }
        if (left[nextIndexLeft] <= right[nextIndexRight]) {
            merged[i] = left[nextIndexLeft];
            nextIndexLeft++;
            continue;
        }
        if (left[nextIndexLeft] > right[nextIndexRight]) {
            merged[i] = right[nextIndexRight];
            nextIndexRight++;
            continue;
        }
    }
    System.out.println("merged : " + Arrays.toString(merged));
    return merged;
}

Просто немного отличается от оригинального решения

Ранга
источник
0

Чтобы пометить два отсортированных массива за O (m + n) сложность времени, используйте подход ниже только с одним циклом. m и n - длина первого массива и второго массива.

public class MargeSortedArray {
    public static void main(String[] args) {
        int[] array = new int[]{1,3,4,7};
        int[] array2 = new int[]{2,5,6,8,12,45};
        int[] newarry = margeToSortedArray(array, array2);
        //newarray is marged array
    }

    // marge two sorted array with o(a+n) time complexity
    public static int[] margeToSortedArray(int[] array, int[] array2) {
        int newarrlen = array.length+array2.length;
        int[] newarr = new int[newarrlen];

        int pos1=0,pos2=0;
        int len1=array.length, len2=array2.length;

        for(int i =0;i<newarrlen;i++) {     
            if(pos1>=len1) {
                newarr[i]=array2[pos2];
                pos2++;
                continue;
            }
            if(pos2>=len2) {
                newarr[i]=array[pos1];
                pos1++;
                continue;
            }

            if(array[pos1]>array2[pos2]) {
                newarr[i]=array2[pos2];
                pos2++;
            } else {
                newarr[i]=array[pos1];
                pos1++;
            }   
        }

        return newarr;
    }

}
Бирбал Сингх
источник
0
var arr1 = [2,10,20,30,100];
var arr2 = [2,4,5,6,7,8,9];
var j = 0;
var i =0;
var newArray = [];

for(var x=0;x< (arr1.length + arr2.length);x++){
    if(arr1[i] >= arr2[j]){                //check if element arr2 is equal and less than arr1 element
        newArray.push(arr2[j]);
      j++;
    }else if(arr1[i] < arr2[j]){            //check if element arr1 index value  is less than arr2 element
        newArray.push(arr1[i]);
        i++;
    }
    else if(i == arr1.length || j < arr2.length){    // add remaining arr2 element
        newArray.push(arr2[j]);
        j++
    }else{                                                   // add remaining arr1 element
        newArray.push(arr1[i]); 
        i++
    }

}

console.log(newArray);
Amar1990
источник
-1

Поскольку вопрос не предполагает какого-либо конкретного языка. Вот решение в Python. Предполагая, что массивы уже отсортированы.

Подход 1 - использование массивов NumPy: импорт NUMPY

arr1 = numpy.asarray([ 1,  2,  3,  4,  5,  6,  7,  8,  9, 11, 14, 15, 55])
arr2 = numpy.asarray([11, 32, 43, 45, 66, 76, 88])

array = numpy.concatenate((arr1,arr2), axis=0)
array.sort()

Подход 2 - Использование списка, при условии, что списки отсортированы.

list_new = list1.extend(list2)
list_new.sort()
Рахул Бисвас
источник
Since the question doesn't assume any specific languageс 2011/5/11/19: 43 он помечен как Java .
седобородый
Ваше решение не использует преимущества того, что списки фактов уже отсортированы, и время его выполнения не равно O (n), так .sort()как O(n log n)в лучшем случае
dark_ruby
-1

Вот моя реализация Java, которая удаляет дубликаты.

public static int[] mergesort(int[] a, int[] b) {
    int[] c = new int[a.length + b.length];
    int i = 0, j = 0, k = 0, duplicateCount = 0;

    while (i < a.length || j < b.length) {
        if (i < a.length && j < b.length) {
            if (a[i] == b[j]) {
                c[k] = a[i];
                i++;j++;duplicateCount++;
            } else {
                c[k] = a[i] < b[j] ? a[i++] : b[j++];
            }
        } else if (i < a.length) {
            c[k] = a[i++];
        } else if (j < a.length) {
            c[k] = b[j++];
        }
        k++;
    }

    return Arrays.copyOf(c, c.length - duplicateCount);
}
kdebugging
источник