Рубрики

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

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

Примеры:

Input: arr[] = {10, 22, 28, 29, 30, 40}, x = 54
Output: 22 and 30

Input: arr[] = {1, 3, 4, 7, 10}, x = 15
Output: 4 and 10

Простым решением является рассмотрение каждой пары и отслеживание ближайшей пары (абсолютная разница между суммой пары и x минимальна). Наконец напечатайте ближайшую пару. Временная сложность этого решения составляет O (n 2 )

Эффективное решение может найти пару за время O (n). Идея похожа на метод 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:  l = 0
       (b) Initialize second  the rightmost index:  r = n-1
3) Loop while l < r.
       (a) If  abs(arr[l] + arr[r] - sum) < diff  then 
           update diff and result 
       (b) Else if(arr[l] + arr[r] <  sum )  then l++
       (c) Else r--    

Ниже приведена реализация вышеуказанного алгоритма.

C ++

// Простая C ++ программа для поиска пары с суммой, ближайшей к заданному номеру.
#include <iostream>
#include <climits>
#include <cstdlib>

using namespace std;

  
// Печатает пару с суммой, ближайшей к x

void printClosest(int arr[], int n, int x)

{

    int res_l, res_r;  // Хранить индексы пары результатов

  

    // Инициализируем левый и правый индексы и разницу между

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

    int l = 0, r = n-1, diff = INT_MAX;

  

    // Пока есть элементы между l и r

    while (r > l)

    {

       // Проверяем, ближе ли эта пара к ближайшей

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

       {

           res_l = l;

           res_r = r;

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

       }

  

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

       if (arr[l] + arr[r] > x)

           r--;

       else // Перейти к большим значениям

           l++;

    }

  

    cout <<" The closest pair is " << arr[res_l] << " and " << arr[res_r];

}

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

int main()

{

    int arr[] =  {10, 22, 28, 29, 30, 40}, x = 54;

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

    printClosest(arr, n, x);

    return 0;

}

Джава

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

import java.io.*;

import java.util.*;

import java.lang.Math;

  

class CloseSum {

      

    // Печатает пару с суммой, близкой к x

    static void printClosest(int arr[], int n, int x)

    {

        int res_l=0, res_r=0// Хранить индексы пары результатов

   

        // Инициализируем левый и правый индексы и разницу между

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

        int l = 0, r = n-1, diff = Integer.MAX_VALUE;

   

        // Пока есть элементы между l и r

        while (r > l)

        {

            // Проверяем, ближе ли эта пара к ближайшей

            if (Math.abs(arr[l] + arr[r] - x) < diff)

            {

               res_l = l;

               res_r = r;

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

            }

   

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

            if (arr[l] + arr[r] > x)

               r--;

            else // Перейти к большим значениям

               l++;

        }

   

    System.out.println(" The closest pair is "+arr[res_l]+" and "+ arr[res_r]);

}

      

      

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

    public static void main(String[] args)

    {

        int arr[] =  {10, 22, 28, 29, 30, 40}, x = 54;

        int n = arr.length;

        printClosest(arr, n, x);        

    }

}
/ * Этот код предоставлен Девешом Агравалом * /

python3

# Python3 программа для поиска пары
# с суммой
# ближе всего к данному нет.

  
# Достаточно большое значение больше
# чем любой
# элемент во входном массиве

MAX_VAL = 1000000000

  

  
# Печатает пару с суммой, ближайшей к x

  

def printClosest(arr, n, x):

      

    # Хранить индексы пары результатов

    res_l, res_r = 0, 0

      

    # Инициализировать левый и правый индексы

    # и разница между

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

    l, r, diff = 0, n-1, MAX_VAL

      

    # Пока есть элементы между l и r

    while r > l:

        # Проверьте, ближе ли эта пара, чем

        # ближайшая пара на данный момент

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

            res_l = l

            res_r = r

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

      

        if arr[l] + arr[r] > x:

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

        # меньшие значения.

            r -= 1

        else:

        # Перейти к большим значениям

            l += 1

          

    print('The closest pair is {} and {}'

         .format(arr[res_l], arr[res_r]))

  

  
# Код драйвера для проверки выше

if __name__ == "__main__":

    arr = [10, 22, 28, 29, 30, 40]

    n = len(arr)

    x=54

    printClosest(arr, n, x)

  
# Этот код предоставлен Tuhin Patra

C #

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

using System;

  

class GFG {

      

    // Печатает пару с суммой, близкой к x

    static void printClosest(int []arr, int n, int x)

    {

          

        // Хранить индексы пары результатов

        int res_l = 0, res_r = 0; 

  

        // Инициализируем левый и правый индексы и

        // разница между суммой пары и х

        int l = 0, r = n-1, diff = int.MaxValue;

  

        // Пока есть элементы между l и r

        while (r > l)

        {

              

            // Проверяем, ближе ли эта пара, чем

            // ближайшая пара на данный момент

            if (Math.Abs(arr[l] + arr[r] - x) < diff)

            {

                res_l = l;

                res_r = r;

                diff = Math.Abs(arr[l] + arr[r] - x);

            }

  

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

            // меньшие значения.

            if (arr[l] + arr[r] > x)

            r--;

            else // Перейти к большим значениям

            l++;

        }

      

        Console.Write(" The closest pair is " +

                 arr[res_l] + " and " + arr[res_r]);

    }

      

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

    public static void Main()

    {

        int []arr = {10, 22, 28, 29, 30, 40};

        int x = 54;

        int n = arr.Length;

          

        printClosest(arr, n, x);     

    }

}

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

PHP

<?php
// Простая PHP-программа для поиска
// пара с суммой, ближайшей к
// дано нет.

  
// Печатает пару с
// сумма ближайшая к x

function printClosest($arr, $n, $x)

{

      

    // Хранить индексы

    // пары результатов

    $res_l;

    $res_r

  

    // Инициализация влево и вправо

    // индексы и разница между

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

    $l = 0; 

    $r = $n - 1;

    $diff = PHP_INT_MAX;

  

    // Пока есть элементы

    // между l и r

    while ($r > $l)

    {

          

        // Проверяем, ближе ли эта пара

        // чем ближайшая пара на данный момент

        if (abs($arr[$l] + $arr[$r] - $x) < 

                                      $diff)

        {

            $res_l = $l;

            $res_r = $r;

            $diff = abs($arr[$l] + $arr[$r] - $x);

        }

      

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

        // перейти к меньшим значениям.

        if ($arr[$l] + $arr[$r] > $x)

            $r--;

              

        // Перейти к большим значениям

        else 

            $l++;

    }

  

    echo " The closest pair is " 

         , $arr[$res_l] ," and " 

         , $arr[$res_r];

}

  

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

    $arr = array(10, 22, 28, 29, 30, 40); 

    $x = 54;

    $n = count($arr);

    printClosest($arr, $n, $x);

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


Выход:

 The closest pair is 22 and 30

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

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

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

0.00 (0%) 0 votes