1

Мне дали задание сложить 2 отсортированных массива:

int[] arrFirst = {1,3,5};
int[] arrSecond = {4,7,9};

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

Например, из двух приведенных выше массивов, должен получится такой:

{1,3,4,5,7,9} 

Запрещено использовать типичные алгоритмы сортировки. Тоесть идея в том что сортировка происходит при сложении. Как-то изловчится через циклы...

7
  • 3
    что значит сложить массивы?
    – Grundy
    17 ноя 2016 в 8:01
  • 2
    Задание противоречивое. Любой алгоритм, выдающий в результате отсортированный массив, по определению является алгоритмом сортировки.
    – Yaant
    17 ноя 2016 в 8:01
  • Да вы правы поменял на типичные.
    – Pavel
    17 ноя 2016 в 8:02
  • 1
    А что понимается под типичными алгоритмами? Сортировка слиянием — это типичный алгоритм или нет?
    – Yaant
    17 ноя 2016 в 8:03
  • Нет слиянием это я даже не слышал, может это то что нужно? А в чем идея?
    – Pavel
    17 ноя 2016 в 8:09

3 ответа 3

6

Как Вам написали выше, используйте сортировку слиянием. То есть создайте массив массив размером как сумма размеров двух складываемых массивов. пойдет добавление в новый массив элементов методом слияния, т.е. берете самые первые элементы у первого и у второго массива и проверяете какой из них меньше. Тот который меньше добавляете в список. на его место вставляете следующий элемент из массива. И опять сравниваете. Вот хорошая статья на хабре с алгоритмом и объяснением

3

Так как массивы уже отсортированы и имеют фиксированную длину, можно завести два индекса указывающие на текущие элементы каждого массива.

Сделать цикл по результирующему массиву и в нем проверять какой из элементов источников меньше - его вставлять в результат, и сдвигать индекс для массива из которого вставляли.

Если один из индексов стал равен длине соответствующего ему массива - проверку можно не делать и сразу вставлять элемент из второго массива.

Примерная реализация цикла:

int firstIndex = 0;
int secondIndex = 0;
for(int i=0; i< result.length;i++) {
    if(firstIndex >= arrFirst.length){
        result[i] = arrSecond[secondIndex];
        secondIndex += 1;
    }else if(secondIndex >= arrSecond.length){
        result[i] = arrFirst[firstIndex];
        firstIndex += 1;
    }else if( arrFirst[firstIndex]<arrSecond[secondIndex]){
        result[i] = arrFirst[firstIndex];
        firstIndex += 1;
    }else{ 
        result[i] = arrSecond[secondIndex];
        secondIndex += 1;
    }
}

Пример на ideone

2
  • 1
    У товарища явно учебное задание, зачем весь-то код за него писать?
    – Roman
    17 ноя 2016 в 15:22
  • @Roman, чтобы был пример
    – Grundy
    17 ноя 2016 в 15:25
0

Вот здесь я объединяю 2 массива (только уникальные значения):

    int[] b = {1, 3, 7, 5};
    int[] a = {3, 5, 11, 9};

    Arrays.sort(a);
    Arrays.sort(b);
    int[] c = new int[a.length + b.length];
    int aI = 0;
    int bI = 0;
    int i = 0;
    while (i < c.length) {
        if (aI == a.length && bI < b.length) {
            c[i] = b[bI++];
        } else if (bI == b.length && aI < a.length) {
            c[i] = a[aI++];
        } else if (bI == b.length && aI == a.length) {
            break;
        } else if (a[aI] < b[bI]) {
            c[i] = a[aI++];
        } else if (a[aI] == b[bI]) {
            c[i] = b[bI++];
            aI++;
        } else if (a[aI] > b[bI]) {
            c[i] = b[bI++];
        }
        i++;
    }
    int[] result = new int[i];
    System.arraycopy(c, 0, result, 0, i);

    System.out.println("result:" + Arrays.toString(result));

Ваш ответ

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

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