• ,

Кухня(); Второй сезон - 77/79



77. Пусть даны неубывающая последовательность действительных чисел a1 ≤ a2 ≤… ≤ аn и действительные числа b1 ≤ b2 ≤… ≤ bm. Требуется указать те места, на которые нужно вставлять элементы последовательности b1, b2, ..., bm в первую последовательность так, чтобы новая последовательность оставалась возрастающей.

Кухня ПРАВИЛА

4 комментария

iZulrad
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 77. Пусть даны неубывающая последовательность действительных чисел a1 ≤ a2 ≤… ≤ аn
 * и действительные числа b1 ≤ b2 ≤… ≤ bm. Т
 * ребуется указать те места, на которые нужно вставлять элементы последовательности b1, b2, ..., bm
 * в первую последовательность так, чтобы новая последовательность оставалась возрастающей.
 */
public class App01 {
    public static void main(String[] args) {
        List<Integer> in = new ArrayList<Integer>() {
            {add(-10); add(2); add(2); add(5); add(10); add(88);}
        };

        List<Integer> from = new ArrayList<Integer>() {
            {add(-1); add(3); add(4); add(7); add(99);}
        };

        List<Integer> indexes = gimmeIndexes(in, from);
        System.out.println("Куда нужно вставлять, с учетом вставки слева направо " + indexes);

        for (int i = 0; i < indexes.size(); i++)  in.add(indexes.get(i), from.get(i));
        System.out.println("После вставки "+ in);
    }

    private static List<Integer> gimmeIndexes(List<Integer> in, List<Integer> from) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < from.size(); i++) {
            int dex = Collections.binarySearch(in, from.get(i));
            if (dex < 0) result.add(-(dex + 1) + i);
            else result.add(dex + i);
        }
        return result;
    }
}
iZulrad
Вывод
Куда нужно вставлять, с учетом вставки слева направо [1, 4, 5, 7, 10]
После вставки [-10, -1, 2, 2, 3, 4, 5, 7, 10, 88, 99]
gnev
  • gnev
  • 0

public class Task77 {

    public static void main(String[] args) {

        int[] a;
        int[] b;
        List<Integer> listA = new LinkedList<>();
        List<Integer> listOfIndex = new LinkedList<>();
        List<Integer> listofIndexWithShift = new LinkedList<>();

        Scanner scanner = new Scanner(System.in);

        System.out.print("Количество элементов В последовательности 'a': ");
        int sizeListA = scanner.nextInt();
        a = fillArray(sizeListA);
        Arrays.sort(a);

        System.out.print("Количество элементов В последовательности 'b': ");
        int sizeListB = scanner.nextInt();
        b = fillArray(sizeListB);
        Arrays.sort(b);

        listOfIndex = findIndexes(a, b);
        listofIndexWithShift = findIndexesShift(a, b);
        System.out.println("Последовательность 'а': " + Arrays.toString(a));
        System.out.println("Последовательность 'b': " + Arrays.toString(b));
        System.out.println("Индексы в последовательности 'a' для вставки элементов последовательности 'b'(без сдвига): " +
                Arrays.toString(listOfIndex.toArray()));
        System.out.println("Индексы в последовательности 'a' для вставки элементов последовательности 'b'(со сдвигом): " +
                Arrays.toString(listofIndexWithShift.toArray()));

        for (int element : a) {
            listA.add(element);
        }

        int i = 0;
        for (Integer integer : listofIndexWithShift) {
            listA.add(integer, b[i++]);
        }
        System.out.println("Результирующая последовательность: " + Arrays.toString(listA.toArray()));

    }

    public static int[] fillArray(int lenght){
        int[] array = new int[lenght];
        Random randomNum = new Random();

        for (int i = 0; i < array.length; i++) {
            array[i] = randomNum.nextInt(500);
        }
        return array;
    }

    public static List<Integer> findIndexes(int[] a, int[] b){
        List<Integer> list = new LinkedList<>();
        for (int i = 0, j = 0; i < a.length && j < b.length;) {
            if ((i == a.length - 1) && (b[j] > a[i])){
                list.add(i+1);
                j++;

            }else if(b[j] <= a[i]){
                list.add(i);
                j++;
            }
            else{
                i++;
            }
        }
        return list;
    }

    public static List<Integer> findIndexesShift(int[] a, int[] b){
        List<Integer> listA = new ArrayList<Integer>();
        for (int element : a) {
            listA.add(element);
        }
        List<Integer>list = new ArrayList<>();

        for (int i = 0, j = 0; i < listA.size() && j < b.length;) {
            if ((i == listA.size() - 1) && (b[j] > listA.get(i))){
                listA.add(i+1, b[j]);
                list.add(i+1);
                j++;

            }else if(b[j] <= listA.get(i)){
                listA.add(i, b[j]);
                list.add(i);
                j++;
                i++;
            }
            else{
                i++;
            }
        }
        return list;
    }
}
gnev
Ввод и вывод
Количество элементов В последовательности 'a': 4
Количество элементов В последовательности 'b': 3
Последовательность 'а': [52, 135, 200, 312]
Последовательность 'b': [106, 170, 274]
Индексы в последовательности 'a' для вставки элементов последовательности 'b'(без сдвига): [1, 2, 3]
Индексы в последовательности 'a' для вставки элементов последовательности 'b'(со сдвигом): [1, 3, 5]
Результирующая последовательность: [52, 106, 135, 170, 200, 274, 312]
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.