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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

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