Рубрики

Java-программа для поиска ближайшей пары из двух отсортированных массивов

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

Нам даны два массива ar1 [0… m-1] и ar2 [0..n-1] и число x, нам нужно найти пару ar1 [i] + ar2 [j] такую, что абсолютное значение (ar1 [i] + ar2 [j] — x) минимально.

Пример:

Input:  ar1[] = {1, 4, 5, 7};
        ar2[] = {10, 20, 30, 40};
        x = 32      
Output:  1 and 30

Input:  ar1[] = {1, 4, 5, 7};
        ar2[] = {10, 20, 30, 40};
        x = 50      
Output:  7 and 40

Джава

// Java программа для поиска ближайшей пары в массиве

class ClosestPair {

    // ar1 [0..m-1] и ar2 [0..n-1] отсортированы по двум

    // массивы /, а x это номер. Эта функция печатает

    // пара из обоих массивов такая, что сумма

    // пара ближе всего к х.

    void printClosest(int ar1[], int ar2[], int m, int n, int x)

    {

        // Инициализируем diff между парой sum и x.

        int diff = Integer.MAX_VALUE;

  

        // res_l и res_r являются индексами результата из ar1 [] и ar2 []

        // соответственно

        int res_l = 0, res_r = 0;

  

        // Начинаем с левой стороны ar1 [] и правой стороны ar2 []

        int l = 0, r = n - 1;

        while (l < m && r >= 0) {

            // Если эта пара ближе к x, чем ранее

            // найти ближайший, затем обновить res_l, res_r и diff

            if (Math.abs(ar1[l] + ar2[r] - x) < diff) {

                res_l = l;

                res_r = r;

                diff = Math.abs(ar1[l] + ar2[r] - x);

            }

  

            // Если сумма этой пары больше чем x, перейти к меньшему

            // боковая сторона

            if (ar1[l] + ar2[r] > x)

                r--;

            else // переместимся в большую сторону

                l++;

        }

  

        // Распечатать результат

        System.out.print("The closest pair is [" + ar1[res_l] + ", " + ar2[res_r] + "]");

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String args[])

    {

        ClosestPair ob = new ClosestPair();

        int ar1[] = { 1, 4, 5, 7 };

        int ar2[] = { 10, 20, 30, 40 };

        int m = ar1.length;

        int n = ar2.length;

        int x = 38;

        ob.printClosest(ar1, ar2, m, n, x);

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

Выход:

The closest pair is [7, 30]

Пожалуйста, обратитесь к полной статье на Найти ближайшую пару из двух отсортированных массивов для более подробной информации!

Рекомендуемые посты:

Java-программа для поиска ближайшей пары из двух отсортированных массивов

0.00 (0%) 0 votes