Как решить проблему с алгоритмом на java?

Question

Задача такова, есть две неубывающие прогрессии, нужно в первую вставить вторую так, чтобы прогрессия осталась неубывающий, а места вставки вывести, т.е. просто все вместить в новый массив и отсортировать не получиться. Мой код:

public static void main(String[] args) {
    int[] array1 = {1, 3, 6, 7, 8, 11, 34, 55, 66, 77, 89, 98, 115};
    int[] array2 = {5, 9, 10, 25, 38, 69, 99};
    int[] result = new int[array1.length + array2.length];
    
    System.out.println("\nМассив 1: ");
    for (int i = 0; i < array1.length; i++) {
        System.out.print(array1[i] + " ");
    }
    
    System.out.println("\nМассив 2: ");
    for (int i = 0; i < array2.length; i++) {
        System.out.print(array2[i] + " ");
    }
    
    int newIndex = 0;
    int indexOfNewArray = 0;
    System.out.println("\nМестно вставки в исходный массив: " );
    for (int j = 0; j < array2.length; j++) {
        for (int i = newIndex; i < array1.length - 1; i++) {
            newIndex = i + 1;
            if (array1[i] > array2[j]) {
                System.out.print((newIndex + 1) + " ");
                result[indexOfNewArray] = array2[j];
                result[indexOfNewArray + 1] = array1[i];
                indexOfNewArray += 2;
                break;
            }
            result[indexOfNewArray] = array1[i];
            indexOfNewArray++;
        }
    }

    System.out.println("\nНовый массив: ");
    for (int i = 0; i < result.length; i++) {
        System.out.print(result[i] + " ");
    }
}

На выходе вот такая ситуация, последние элементы не заносятся

Answer 1

Я бы убрал в вашем решении вложенные for, сделал бы один цикл, например, так:

int index1 = 0;
int index2 = 0;
int resultIndex = 0;
System.out.println("Место вставки в исходный массив:");
while (index1 < array1.length && index2 < array2.length) {
    int value1 = array1[index1];
    int value2 = array2[index2];
    if (value1 < value2) {
        result[resultIndex] = value1;
        resultIndex++;
        index1++;
    } else {
        result[resultIndex] = value2;
        resultIndex++;
        index2++;
        System.out.print(resultIndex + " ");
    }
}

Answer 2

Простите, а почему не получится отсортировать:

public static void main(String[] args) {
    int[] array1 = {1, 3, 6, 7, 8, 11, 34, 55, 66, 77, 89, 98, 115};
    int[] array2 = {5, 9, 10, 25, 38, 69, 99};

    int[] result = getPositions(concat(array1, array2), array2);

    System.out.println(Arrays.toString(result));
}

private static int[] concat(int[] arr1, int[] arr2) {
    return IntStream.concat(Arrays.stream(arr1), Arrays.stream(arr2)).sorted().toArray();
}

private static int[] getPositions(int[] arr1, int[] arr2) {
    int[] positions = new int[arr2.length];
    int index = 0;
    for (int i = 0; i < arr1.length; i++) {
        if (arr1[i] == arr2[index]) positions[index++] = i;
        if (index >= arr2.length) break;
    }
    return positions;
}

Answer 3

Алгоритм такой, на джаву сам перепишешь:

var a = [1, 3, 6, 7, 8, 11, 34, 55, 66, 77, 89, 98, 115]
var b = [5, 9, 10, 25, 38, 69, 99]

var res = new Array(a.length + b.length)
var i = new Array(b.length)
var q, w, e

for (q = w = e = 0; q < a.length && w < b.length; ++e) {
  if (a[q] < b[w]) {
    res[e] = a[q++]
  } else {
    i[w] = q
    res[e] = b[w++]
  }
}

for (; q < a.length; ++q, ++e) {
  res[e] = a[q]
}

for (; w < b.length; ++w, ++e) {
  i[w] = q
  res[e] = b[w]
}

console.log("Массив 1:", a.join(" "))
console.log("Массив 2:", b.join(" "))
console.log("Места вставки:", i.join(" "))
console.log("Результат:", res.join(" "))

Answer 4

Зачем выдумывать велосипед? В Apache Commons уже есть утилита: https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/CollectionUtils.html

Пример:

var list1 = List.of(1, 3, 6, 7, 8, 11, 34, 55, 66, 77, 89, 98, 115);
var list2 = List.of(5, 9, 10, 25, 38, 69, 99);
var result = CollectionUtils.collate(list1, list2).toArray(Integer[]::new);

БЛОГ НА HUSL

Как решить проблему с алгоритмом на java?

Ответы (4 шт):