Берілген айырмашылықпен барлық жұптарды табыңыз

Проблемалық мәлімдеме

Біз ан массив массивте әр түрлі элементтер бар немесе қайталанатын элементтер жоқ. Берілген айырмашылықпен барлық жұптарды табыңыз. Егер берілген әр түрлі жұп болмаса, басып шығарыңыз «Әр түрлі берілген жұп болмайды».

мысал

енгізу

10 20

90 70 20 80 50 25 35 15 100 150

шығыс

90 70

70 50

80 100

35 15 (20 айырмашылығы бар элементтер жұбы шығады)

Берілген айырмашылықпен барлық жұптарды табуға арналған 1-тәсіл

Массивтен бір элементті таңдайтын екі циклды іске қосыңыз. 0 индексінен бастап, берілген айырмашылықпен жұп алу үшін массивті асыға күтіңіз.

а) Егер элементті тапсақ, оларды басып шығарыңыз.
б) Басқа баспа, табылған жоқ.

Іске асыру

Берілген айырмашылықпен барлық жұптарды табуға арналған C ++ бағдарламасы

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,d;
  cin>>n>>d;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  int flag=0;
  for(int i=0;i<n;i++)//select an element
  {
    for(int j=i+1;j<n;j++) // look forward in the array
        if(abs(a[i]-a[j])==d)//if we get a pair with given difference then success
        {
          cout<<a[i]<<"  "<<a[j]<<endl;
          flag=1;
        }
  }
  if(flag==0)
  cout<<"No pair with given different";
}

Берілген айырмашылықпен барлық жұптарды табуға арналған Java бағдарламасы

import java.util.Scanner;
class sum
{
    public static int abs(int x)
    {
        if(x<0)
        {
            x*=-1;
        }
        return x;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int d = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int flag=0;
        for(int i=0;i<n;i++)//select an element
        {
          for(int j=i+1;j<n;j++) // look forward in the array
              if(abs(a[i]-a[j])==d)//if we get a pair with given difference then success
              {
                System.out.println(a[i]+"  "+a[j]);
                flag=1;
              }
        }
        if(flag==0)
        System.out.println("No pair with given different");
    }
}

10 20
90 70 20 80 50 25 35 15 100 150

90  70
70  50
80  100
35  15

Күрделілікті талдау

Уақыттың күрделілігі

O (N * N) мұндағы N - берілген жиымның өлшемі. Екі циклды екі циклмен жүгіріп, әр жұпты тексеріңіз.

Ғарыштың күрделілігі

O (1) өйткені біз бұл жерде артық орынды қолданбаймыз.

Берілген айырмашылықпен барлық жұптарды табуға арналған 2-тәсіл

Қадам 1: Алдымен берілген жиымды сұрыптаңыз. Ол O (NlogN) алады.

Қадам 2: Бірінші алгоритм сияқты бірінші элементтен басталатын әр элемент үшін сәйкес келетін жұпты табыңыз.

и) Мұнда элементті табу үшін екілік іздеуді қолданамыз.
іі) а элементі және берілген айырмашылық n үшін а + n іздейміз.

мысал

енгізу

10 20

90 70 20 80 50 25 35 15 100 150

Айырмасы = 20 болатын барлық жұп элементтерді табыңыз

Алгоритмді енгізу массивінде қолдану,

Біртіндеп жұмыс істеу

1. Массивті сұрыптау, сұрыпталған массив: 15 20 25 35 50 70 80 90 100 150
2. a = 15, айырым (n) = 20 сондықтан, a + n = 35, binary_search (35, енгізу жиымы) = True. Басып шығару 15 35. Алға қарай жылжытыңыз
3. a = 20, айырым (n) = 20 сондықтан, a + n = 40, binary_search (40, енгізу жиымы) = Жалған. Алға жылжу
4. a = 25, айырым (n) = 20 сондықтан, a + n = 45, binary_search (45, енгізу жиымы) = Жалған. Алға жылжу
5. a = 35, айырым (n) = 20 сондықтан, a + n = 55, binary_search (55, енгізу жиымы) = Жалған. Алға жылжу
6. a = 50, айырым (n) = 20 сондықтан, a + n = 70, binary_search (70, енгізу жиымы) = True. Басып шығару 50 70. Алға қарай жылжытыңыз
7. a = 70, айырым (n) = 20 сондықтан, a + n = 90, binary_search (90, енгізу жиымы) = True. Басып шығару 70 90. Алға қарай жылжытыңыз
8. a = 80, айырым (n) = 20 сондықтан, a + n = 100, binary_search (100, енгізу жиымы) = True. Басып шығару 80 100. Алға қарай жылжытыңыз
9. a = 90, айырмашылық (n) = 20 сондықтан, a + n = 110, binary_search (110, енгізу жиымы) = Жалған. Алға жылжу
10. a = 100, айырым (n) = 20 сондықтан, a + n = 120, binary_search (120, енгізу жиымы) = жалған. Ілмектің соңы.

Іске асыру

Берілген айырмашылықпен барлық жұптарды табуға арналған C ++ бағдарламасы

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,d;
  cin>>n>>d;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  sort(a,a+n);
  int flag=0;
  for(int i=0;i<n-1;i++)//select an element
  {
      int diff=a[i]+d;
      if(binary_search(a,a+n,diff))
      {
          cout<<a[i]<<" "<<diff<<endl;
          flag=1;
      }
  }
  if(flag==0)
  cout<<"No pair with given different";
}

Берілген айырмашылықпен барлық жұптарды табуға арналған Java бағдарламасы

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static int abs(int x)
    {
        if(x<0)
        {
            x*=-1;
        }
        return x;
    }
    public static int binary_search(int arr[], int l, int r, int x)
    {
        if (r >= l) 
        {
            int mid = l + (r - l) / 2;
            if (arr[mid] == x)
                return mid;
            if (arr[mid] > x)
                return binary_search(arr, l, mid - 1, x);
            return binary_search(arr, mid + 1, r, x);
        }
        return -1;
    }
    
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int d = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        Arrays.sort(a);
        int flag=0;
        for(int i=0;i<n-1;i++)//select an element
        {
            int diff=a[i]+d;
            if(binary_search(a,0,n-1,diff)!=-1)
            {
                System.out.println(a[i]+"  "+diff);
                flag=1;
            }
        }
        if(flag==0)
         System.out.println("No pair with given different");
    }
}

10 20
90 70 20 80 50 25 35 15 100 150

15 35
50 70
70 90
80 100

Үздік сұхбат сұрақтары