Рубрики

Найти пару с заданной разницей

Учитывая несортированный массив и число n, найдите, существует ли в массиве пара элементов, разница которых равна n.

Примеры:

Input: arr[] = {5, 20, 3, 2, 50, 80}, n = 78
Output: Pair Found: (2, 80)

Input: arr[] = {90, 70, 20, 80, 50}, n = 45
Output: No Such Pair

Самый простой способ — запустить два цикла, внешний цикл выбирает первый элемент (меньший элемент), а внутренний цикл ищет элемент, выбранный внешним циклом, плюс n. Временная сложность этого метода составляет O (n ^ 2).

Мы можем использовать сортировку и бинарный поиск, чтобы улучшить временную сложность до O (nLogn). Первым шагом является сортировка массива в порядке возрастания. После того, как массив отсортирован, просмотрите массив слева направо и для каждого элемента arr [i] выполните двоичный поиск arr [i] + n в arr [i + 1..n-1]. Если элемент найден, верните пару.
На первом и втором шагах выполняется O (nLogn). Таким образом, общая сложность O (nLogn).

Второй шаг вышеупомянутого алгоритма может быть улучшен до O (n). Первый шаг остается таким же. Идея для второго шага — взять две индексные переменные i и j, инициализировать их как 0 и 1 соответственно. Теперь запустите линейный цикл. Если arr [j] — arr [i] меньше n, нам нужно искать больший arr [j], поэтому приращение j. Если arr [j] — arr [i] больше n, нам нужно искать большее значение arr [i], поэтому приращение i. Спасибо Аашишу Барнвалу за предложение такого подхода.
Следующий код предназначен только для второго шага алгоритма, он предполагает, что массив уже отсортирован.

C ++

// C ++ программа для поиска пары с заданной разницей
#include <bits/stdc++.h>

using namespace std;

  
// Функция предполагает, что массив отсортирован

bool findPair(int arr[], int size, int n) 

    // Инициализировать позиции двух элементов

    int i = 0; 

    int j = 1; 

  

    // Поиск пары

    while (i < size && j < size) 

    

        if (i != j && arr[j] - arr[i] == n) 

        

            cout << "Pair Found: (" << arr[i] <<

                        ", " << arr[j] << ")"

            return true

        

        else if (arr[j]-arr[i] < n) 

            j++; 

        else

            i++; 

    

  

    cout << "No such pair"

    return false

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

int main() 

    int arr[] = {1, 8, 30, 40, 100}; 

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

    int n = 60; 

    findPair(arr, size, n); 

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

// C программа для поиска пары с заданной разницей
#include <stdio.h>

  
// Функция предполагает, что массив отсортирован

bool findPair(int arr[], int size, int n)

{

    // Инициализировать позиции двух элементов

    int i = 0;  

    int j = 1;

  

    // Поиск пары

    while (i<size && j<size)

    {

        if (i != j && arr[j]-arr[i] == n)

        {

            printf("Pair Found: (%d, %d)", arr[i], arr[j]);

            return true;

        }

        else if (arr[j]-arr[i] < n)

            j++;

        else

            i++;

    }

  

    printf("No such pair");

    return false;

}

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

int main()

{

    int arr[] = {1, 8, 30, 40, 100};

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

    int n = 60;

    findPair(arr, size, n);

    return 0;

}

Джава

// Java программа для поиска пары с заданной разницей

import java.io.*;

  

class PairDifference

{

    // Функция предполагает, что массив отсортирован

    static boolean findPair(int arr[],int n)

    {

        int size = arr.length;

  

        // Инициализировать позиции двух элементов

        int i = 0, j = 1;

  

        // Поиск пары

        while (i < size && j < size)

        {

            if (i != j && arr[j]-arr[i] == n)

            {

                System.out.print("Pair Found: "+

                                 "( "+arr[i]+", "+ arr[j]+" )");

                return true;

            }

            else if (arr[j] - arr[i] < n)

                j++;

            else

                i++;

        }

  

        System.out.print("No such pair");

        return false;

    }

  

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

    public static void main (String[] args)

    {

        int arr[] = {1, 8, 30, 40, 100};

        int n = 60;

        findPair(arr,n);

    }

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

питон

# Python программа для поиска пары с заданной разницей

  
# Функция предполагает, что массив отсортирован

def findPair(arr,n):

  

    size = len(arr)

  

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

    i,j = 0,1

  

    # Поиск пары

    while i < size and j < size:

  

        if i != j and arr[j]-arr[i] == n:

            print "Pair found (",arr[i],",",arr[j],")"

            return True

  

        elif arr[j] - arr[i] < n:

            j+=1

        else:

            i+=1

    print "No pair found"

    return False

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

arr = [1, 8, 30, 40, 100]

n = 60

findPair(arr, n)

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

C #

// C # программа для поиска пары с заданной разницей

using System;

  

class GFG {

      

    // Функция предполагает, что массив отсортирован

    static bool findPair(int []arr, int n)

    {

        int size = arr.Length;

  

        // Инициализировать позиции двух элементов

        int i = 0, j = 1;

  

        // Поиск пары

        while (i < size && j < size)

        {

            if (i != j && arr[j] - arr[i] == n)

            {

                Console.Write("Pair Found: " 

                + "( " + arr[i] + ", " + arr[j] +" )");

                  

                return true;

            }

            else if (arr[j] - arr[i] < n)

                j++;

            else

                i++;

        }

  

        Console.Write("No such pair");

          

        return false;

    }

  

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

    public static void Main ()

    {

        int []arr = {1, 8, 30, 40, 100};

        int n = 60;

          

        findPair(arr, n);

    }

}

  
// Этот код предоставлен Sam007.

PHP

<?php 
// PHP программа для поиска пары с
// заданная разница

  
// Функция предполагает, что
// массив отсортирован

function findPair(&$arr, $size, $n)

{

    // Инициализировать позиции

    // два элемента

    $i = 0; 

    $j = 1;

  

    // Поиск пары

    while ($i < $size && $j < $size)

    {

        if ($i != $j && $arr[$j] - 

                        $arr[$i] == $n)

        {

            echo "Pair Found: " . "("

                  $arr[$i] . ", " . $arr[$j] . ")";

            return true;

        }

        else if ($arr[$j] - $arr[$i] < $n)

            $j++;

        else

            $i++;

    }

  

    echo "No such pair";

    return false;

}

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

$arr = array(1, 8, 30, 40, 100);

$size = sizeof($arr);

$n = 60;

findPair($arr, $size, $n);

  
// Этот код добавлен
// ChitraNayal
?>

Выход:

Pair Found: (40, 100)

Хеширование также может быть использовано для решения этой проблемы. Создайте пустую хеш-таблицу HT. Пройдите по массиву, используйте элементы массива в качестве хеш-ключей и введите их в HT. Пройдите через массив и снова найдите значение n + arr [i] в HT.

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

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

Найти пару с заданной разницей

0.00 (0%) 0 votes