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

Question

Есть код, для задания он выполняется долго, как его можно оптимизировать?

import java.util.Scanner;

public class Main
{
    static Scanner scanner = new Scanner(System.in);

    static void input(int[] array, int length)
    {
        for (int i = 0; i < length; ++i)
            array[i] = scanner.nextInt();
    }

    public static void main(String[] args)
    {
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] array = new int[n];
        int[] array_search = new int[m];

        input(array, n);
        input(array_search, m);

        for (int search = 0; search < m; ++search)
        {
            int value = 0;
            for (int i = 0; i < n; ++i)
            {
                if (array[i] == array_search[search])
                    value = i + 1;
            }
            array_search[search] = value;
        }

        for (int i : array_search)
            System.out.print(i + " ");
    }
}

Задача:

Answer 1

Из условия массив чисел, отсортированных в неубывающем порядке имеем - массив отсортирован. К сортированному массиву можно применить бинарный поиск временная сложность которого O(log n). Временная сложность вашего текущего алгоритма O(n). Единственное, не забудьте учесть условие "про правый индекс".

Попробуйте реализовать бинарный поиск сами, но если что, можно посмотреть реализацию тут

Answer 2

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

Пример

    int[] array = new int[3];
    int[] array_search = new int[3];

    array[0] = 1;
    array[1] = 3;
    array[2] = 5;

    array_search[0] = 1;
    array_search[1] = 5;
    array_search[2] = 7;


    Map<Integer, Integer> map = new HashMap<>();
    for (int i = array.length - 1; i >= 0; i--)
        if (!map.containsKey(array[i]))
            map.put(array[i], i);

    for (int i = 0; i < array_search.length; i++)
        if (map.containsKey(array_search[i]))
            System.out.println(map.get(array_search[i]) + 1);
        else
            System.out.println("0");

БЛОГ НА HUSL

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

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