Бо фарқи додашуда ҷуфтро ёбед


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Amazon Блумберг Citrix Expedia Голдман Sachs Microsoft Nvidia Oracle Salesforce Тиллио Twitter Visa VMware
Ҷустуҷӯи бинарӣ Ҷустуҷӯ Sorting

Изҳороти мушкилот

Дар ин номуайян асал, ҷуфти элементҳоро дар массиви додашуда бо фарқи додашудаи n пайдо кунед.

мисол

вуруди

arr [] = {120, 30, 70, 20, 5, 6},

тафовут (n) = 40

Натиҷаи

[30, 70]

Шарҳ

Дар ин ҷо фарқи 30 ва 70 ба арзиши n баробар аст.

вуруди

arr [] = {120, 30, 70, 20, 5, 6},

тафовут (n) = 10

Натиҷаи

[20, 30]

Шарҳ

Дар ин ҷо фарқи 20 ва 30 ба арзиши n баробар аст.

вуруди

arr = {120, 30, 70, 20, 5, 6},

тафовут (n) = 30

Натиҷаи

Бо фарқи додашуда ягон ҷуфт ёфт нашуд

Шарҳ

Дар ин ҷо ягон чунин ҷуфт мавҷуд нест, ки фарқи байни онҳо ба n баробар бошад.

Алгоритми ҷустуҷӯи ҷуфт бо фарқи додашуда

Ҳоло мо баёнияи мушкилотро медонем. Ҳамин тавр, зуд ба қисми алгоритм гузаред. Мо аввал массиви додашударо ҷудо мекунем ва сипас тамоми массивро убур мекунем. Мо аввал дар индекси 0 ду ва дар индекси дуюм дуввумро мегирем. Ҳоло агар фарқияти байни онҳо аз фарқияти додашуда камтар бошад, пас нишоннамои дуввумро ба 1 ҳаракат диҳед. Агар фарқи байни онҳо аз фарқи додашуда зиёдтар бошад, пас нишондиҳандаи аввалро ба 1 ҳаракат кунед Агар фарқи байни унсурҳо яксон бошад, пас посухро ҳисоб кунед. Ниҳоят, шумораи умумии ҳисобҳоро чоп кунед.

1: Аввал массиви додашударо ҷобаҷо кунед.

2: Дар ин массив, ду индекси i -ро гиред ва j i = 0 ва j = 1 -ро сар кунед.

3: Доираро иҷро кунед, то массиви [j] - массиви [i] = n,

  • Агар массиви [j] - массиви [i] = n, массиви [j] ва массиви [i] -ро чоп кунед.
  • Санҷед, Агар массиви [j] - массиви [i]> n, афзоиши i.
  • Агар массиви [j] - массиви [i] <n, афзоиши j.

4: Агар ҳалқа ба охир расад. Пас чоп кунед 'ягон ҷуфт ёфт нашуд'.

татбиќи

Барномаи C ++ барои дарёфти ҷуфт бо фарқи додашуда

#include <bits/stdc++.h>
using namespace std;
 
//In the given array -> array[] of N N 
//finding the pair with difference n
int FindPair(int array[], int N, int difference)
{
    //sort the given array
    sort(array, array+N);
    int i = 0;  
    int j = 1;
    while(i<N && j<N)
    {
        if (i != j && array[j]-array[i] == difference)
        {
            cout<<"pair with difference "<<difference<<" is: ";
            cout<<"["<<array[i]<<", "<<array[j]<<"]";
            return 1;
        }
        //if difference here is less than given difference
        // move right pointer(j)
        else if (array[j]-array[i] < difference) 
        {
            j++;
        }
        //if difference here is greater than given difference
        // move left pointer(i)
        else
        {
            i++;
        }
    }
    cout<<"No pair found";
    return 0;
}
 
//Main function to check above functions
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int diff;
    cin>>diff;
    FindPair(a, n, diff);
    return 0;
}

Барномаи Java барои дарёфти ҷуфт бо фарқияти додашуда

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    //In the given array -> array[] of N N 
    //finding the pair with difference n
    public static int FindPair(int array[], int N, int difference)
    {
        //sort the given array
        Arrays.sort(array);
        int i = 0;  
        int j = 1;
        while(i<N && j<N)
        {
            if (i != j && array[j]-array[i] == difference)
            {
                System.out.println(array[i] + " " + array[j]);
                return 1;
            }
            //if difference here is less than given difference
            // move right pointer(j)
            else if (array[j]-array[i] < difference) 
            {
                j++;
            }
            //if difference here is greater than given difference
            // move left pointer(i)
            else
            {
                i++;
            }
        }
        System.out.println("No pair found");
        return 0;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        } 
        int diff ;
        diff = sr.nextInt();
        FindPair(arr,n,diff);
    } 
}
6 
5 20 3 2 50 80
78
2 80

Таҳлили мураккабӣ

Мураккабии вақт

О (NLogN) ки дар он n андозаи массив аст. Дар ин ҷо мо функсияи ҷобаҷогузории дохилиро истифода мебарем, ки моро ба мураккабии вақти nlogn мерасонад.

Мураккабии фазо

О (1) зеро мо ҳангоми ҳисоб кардани натиҷа фазои иловагӣ эҷод намекунем.

Адабиёт