Рубрики

Найти ближайшую пару из двух отсортированных массивов

Учитывая два отсортированных массива и число 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

Мы настоятельно рекомендуем свернуть ваш браузер и попробовать это в первую очередь.

Простое решение — запустить два цикла. Внешний цикл рассматривает каждый элемент первого массива, а внутренний цикл проверяет пару во втором массиве. Мы отслеживаем минимальную разницу между ar1 [i] + ar2 [j] и x.

Мы можем сделать это за O (n) время, используя следующие шаги.
1) Объединить данные двух массивов во вспомогательный массив размером m + n, используя процесс слияния сортировки слиянием . При объединении сохраните другой логический массив размером m + n, чтобы указать, является ли текущий элемент в объединенном массиве аргументом ar1 [] или ar2 [].

2) Рассмотрим объединенный массив и используем алгоритм линейного времени, чтобы найти пару с суммой, ближайшей к x . Еще одна вещь, которую нам нужно рассмотреть только те пары, которые имеют один элемент из ar1 [] и другой из ar2 [], мы используем для этого логический массив.

Можем ли мы сделать это за один проход и O (1) лишний пробел?
Идея состоит в том, чтобы начать с левой стороны одного массива и правой стороны другого массива и использовать алгоритм, аналогичный шагу 2 вышеприведенного подхода. Ниже приводится подробный алгоритм.

1) Initialize a variable diff as infinite (Diff is used to store the 
   difference between pair and x).  We need to find the minimum diff.
2) Initialize two index variables l and r in the given sorted array.
       (a) Initialize first to the leftmost index in ar1:  l = 0
       (b) Initialize second  the rightmost index in ar2:  r = n-1
3) Loop while  l = 0
       (a) If  abs(ar1[l] + ar2[r] - sum) < diff  then 
           update diff and result 
       (b) If (ar1[l] + ar2[r] <  sum )  then l++
       (c) Else r--    
4) Print the result. 

Ниже приводится реализация этого подхода.

C ++

// C ++ программа для поиска пары из двух отсортированных массивов, таких
// что сумма пары ближе всего к данному числу x
#include <iostream>
#include <climits>
#include <cstdlib>

using namespace std;

  
// 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 = INT_MAX;

  

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

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

    int res_l, res_r;

  

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

    int l = 0, r = n-1;

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

    {

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

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

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

       {

           res_l = l;

           res_r = r;

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

       }

  

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

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

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

           r--;

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

           l++;

    }

  

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

    cout << "The closest pair is [" << ar1[res_l] << ", "

         << ar2[res_r] << "] \n";

}

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

int main()

{

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

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

    int m = sizeof(ar1)/sizeof(ar1[0]);

    int n = sizeof(ar2)/sizeof(ar2[0]);

    int x = 38;

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

    return 0;

}

Джава

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

    }

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

python3

# Python3 программа для поиска пары из
# два отсортированных массива так, что сумма
# пары ближе всего к данному числу x

import sys

  
# ar1 [0..m-1] и ar2 [0..n-1] два
# дано отсортированных массивов и дано x
# число. Эта функция печатает пару
# из обоих массивов, так что сумма
# пары ближе всего к х.

def printClosest(ar1, ar2, m, n, x):

  

    # Инициализировать разницу между

    # сумма пары и х.

    diff=sys.maxsize

  

    # res_l и res_r - результат

    # индексы из ar1 [] и ar2 []

    # соответственно. Начать слева

    # сторона ar1 [] и правая сторона ar2 []

    l = 0

    r = n-1

    while(l < m and r >= 0):

      

    # Если эта пара ближе к х, чем

    # ранее найденный ближайший,

    # затем обновите res_l, res_r и diff

        if abs(ar1[l] + ar2[r] - x) < diff:

            res_l = l

            res_r = r

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

      

  

    # Если сумма этой пары больше, чем х,

    # перейти на меньшую сторону

        if ar1[l] + ar2[r] > x:

            r=r-1

        else: # перейти в большую сторону

            l=l+1

      

  

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

    print("The closest pair is [",

         ar1[res_l],",",ar2[res_r],"]")

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

ar1 = [1, 4, 5, 7]

ar2 = [10, 20, 30, 40]

m = len(ar1)

n = len(ar2)

x = 38

printClosest(ar1, ar2, m, n, x)

  
# Этот код предоставлен Смитой Динеш Семвал

C #

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

using System;

  

class GFG {

      

    // ar1 [0..m-1] и ar2 [0..n-1] два

    // даны отсортированные массивы / и дан х

    // число. Эта функция печатает

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

    // сумма пары ближайшая к х.

    static void printClosest(int []ar1,

            int []ar2, int m, int n, int x)

    {

          

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

        // сумма и х.

        int diff = int.MaxValue;

  

        // результат 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)

        {

              

            // Если эта пара ближе к

            // х, чем ранее

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

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

            }

      

            // Если сумма этой пары больше

            // чем х, перейти к меньшему

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

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

                r--;

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

                l++;

        }

  

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

        Console.Write("The closest pair is [" 

                          + ar1[res_l] + ", "

                         + ar2[res_r] + "]");

    }

  

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

    public static void Main()

    {

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

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

        int m = ar1.Length;

        int n = ar2.Length;

        int x = 38;

          

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

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP программа для поиска пары
// из двух отсортированных массивов таких
// что сумма пары равна
// ближе всего к данному числу x

  
// ar1 [0..m-1] и ar2 [0..n-1]
// два заданных отсортированных массива
// и х это номер. Эта
// функция печатает пару из
// оба массива такие, что сумма
// пары ближе всего к х.

function printClosest($ar1, $ar2,

                      $m, $n, $x)

{

      

    // Инициализируем разницу между

    // пара сумм и х.

    $diff = PHP_INT_MAX;

  

    // результат res_l и res_r

    // индексы из ar1 [] и ar2 []

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

    $res_l

    $res_r;

  

    // Начинаем с левой стороны

    // ar1 [] и правая часть ar2 []

    $l = 0;

    $r = $n - 1;

    while ($l < $m and $r >= 0)

    {

          

        // Если эта пара ближе к

        // х, чем ранее

        // нашли ближайший, то

        // обновляем res_l, res_r и

        // diff

        if (abs($ar1[$l] + $ar2[$r] - 

                       $x) < $diff)

        {

            $res_l = $l;

            $res_r = $r;

            $diff = abs($ar1[$l] +

                    $ar2[$r] - $x);

        }

      

        // Если сумма этой пары равна

        // больше чем x, перейти к меньшему

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

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

            $r--;

              

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

        else 

            $l++;

    }

  

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

    echo "The closest pair is [" , $ar1[$res_l] , ", "

                               , $ar2[$res_r] , "] \n";

}

  

    // Код драйвера

    $ar1 = array(1, 4, 5, 7);

    $ar2 = array(10, 20, 30, 40);

    $m = count($ar1);

    $n = count($ar2);

    $x = 38;

    printClosest($ar1, $ar2, $m, $n, $x);

  
// Этот код предоставлен anuj_67.
?>


Выход:

 The closest pair is [7, 30] 

Пара значений наименьшего различия между двумя несортированными массивами

Эта статья предоставлена Harsh. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

Найти ближайшую пару из двух отсортированных массивов

0.00 (0%) 0 votes