Bir cərgədə iki ədədi arasında minimum məsafəni tapın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Paytm Über
GeyimBaxılıb 1305

Problem bəyanat

Verilmiş çeşidlənməmişdir arraydublikatları da ehtiva edə bilən bir sıra içərisində iki fərqli rəqəm arasındakı minimum məsafəni tapın.

Bir sıra içindəki 2 rəqəm arasındakı məsafə: indekslər arasındakı mütləq fərq +1.

misal

Input

12

3 5 4 2 6 5 6 6 5 4 8 3

3 6

Buraxılış

4

Yanaşma 1

  1. İki döngədən istifadə edin, bir döngə elementlərdən birini tapır, ikinci döngə digər elementi eyni şəkildə tapır.
  2. Aralarındakı məsafəni aldığımız indeksləri çıxartın.
  3. Minimum məsafəni əldə edənə qədər bunu edin.

Həyata keçirilməsi

Üçün C ++ Proqramı Bir cərgədə iki ədədi arasında minimum məsafəni tapın

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    int X , Y;
    cin>>X>>Y; //the elements between which minimum distance is to be found
    int min_dist = INT_MAX;
    for(int i=0; i<n; i++) //select one element
    {  
      for(int j=i+1; j<n; j++) //traverse ahead
      {
        if(arr[i] == X and arr[j] == Y) // if we get X and Y we try to update the minimum distance
        min_dist = min(min_dist , abs(i-j));
        if(arr[i] == Y and arr[j] == X)
        min_dist = min(min_dist , abs(i-j));          
      }
    }
    cout<<min_dist;
  return 0;
}

Üçün Java Proqramı Bir cərgədə iki ədədi arasında minimum məsafəni tapın

import static java.lang.Math.min;
import java.util.Scanner;

class sum
{
    public static int abs(int x)
    {
        if(x<0)
            x=x*-1;
        return x;
    }
    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 X = sr.nextInt(); int Y = sr.nextInt(); //the elements between which minimum distance is to be found
        int min_dist = 10000000;
        for(int i=0; i<n; i++) //select one element
        {  
          for(int j=i+1; j<n; j++) //traverse ahead
          {
            if(arr[i] == X && arr[j] == Y) // if we get X and Y we try to update the minimum distance
            min_dist = min(min_dist , abs(i-j));
            if(arr[i] == Y && arr[j] == X)
            min_dist = min(min_dist , abs(i-j));          
          }
        }
        System.out.println(min_dist);
    }
}
12
3 5 4 2 6 5 6 6 5 4 8 3
3 6
4

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n ^ 2) hara n massivin ölçüsüdür. Burada x üçün indeks tapmaq üçün biri, y üçün indeks tapmaq üçün iki döngə işlədirik. İndi hər bir dəyər üçün mümkün olan hər cütün minimumunu tapın.

Kosmik Mürəkkəblik

O (1) çünki burada heç bir köməkçi yerdən istifadə etmirik.

Alqoritm 2

1 Adım: X, Y-nin olduğu yer i, j olsun.

  1. İ, j-ni 0 ilə başlayın.

2 Adım: İ və j massivin ölçüsündən az olması üçün bir döngə işlədin. Elementlərdən birini alsaq, başqa bir element əldə edənə qədər sadəcə döngə edirik.

  1. Massivin ölçüsü N olsun, j-də X var, sonra j-dən N-ə döngə edirik.

3 Adım: İndi ikinci elementi indekslər arasındakı fərqlə tapdıqdan sonra minimum məsafəni yeniləyirik.

  1. İ-ni j (i = j) olaraq yeniləyin.
  2. çünki ikinci elementi tapdığımız yerdən yenidən keçməyə başlamalıyıq.
  3. Aralarındakı minimum məsafəni alana qədər digər cütü verildiyi kimi tapmaq üçün.
  4. Beləliklə, hər dəfə minimum məsafəni bütün məsafəni keçməyimizə qədər yeni məsafə ilə müqayisə edərək yeniləyirik.

4 Adım: minimum məsafəni nəhayət çap edirik

Həyata keçirilməsi

Bir sıra iki rəqəm arasındakı minimum məsafəni tapmaq üçün C ++ proqramı

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int N;
    cin>>N;
    int arr[N];
    for(int i=0;i<N;i++)
    {
        cin>>arr[i];
    }  
  int X , Y;
  cin>>X>>Y; //the elements between which minimum distance is to be found
  int min_dist = INT_MAX;
  int i = 0, j = 0; //i and j to point at X and Y present somewhere in the array
  while(i < N and j < N)
  {
    if(arr[i] == X) //if we get X
      {
        while( j < N and arr[j] != Y) // we simply loop till we get Y
          j++;  
        if(j < N and arr[j] == Y)
        min_dist = min(min_dist,abs(i-j));//we update the minimum distance if required
        
        i = j; // important step because as we got X,Y pair we can stand at present position and loop forward for another pair
      }
    else if(arr[i] == Y)
    {
        while( j < N and arr[j] != X)
          j++;
          
        if(j < N and arr[j] == X)
        min_dist = min(min_dist,abs(i-j));
      i = j;
    }
    else
     i++;
  }
  cout<<min_dist;
  return 0;
}

Üçün Java Proqramı Bir cərgədə iki ədədi arasında minimum məsafəni tapın

import static java.lang.Math.min;
import java.util.Scanner;

class sum
{
    public static int abs(int x)
    {
        if(x<0)
            x=x*-1;
        return x;
    }
    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 X = sr.nextInt(); int Y = sr.nextInt(); //the elements between which minimum distance is to be found
        int min_dist = 10000000;
        int i = 0, j = 0; //i and j to point at X and Y present somewhere in the array
        while(i < n && j < n)
        {
          if(arr[i] == X) //if we get X
            {
              while( j < n && arr[j] != Y) // we simply loop till we get Y
                j++;  
              if(j < n && arr[j] == Y)
              min_dist = min(min_dist,abs(i-j));//we update the minimum distance if required
              i = j; // important step because as we got X,Y pair we can stand at present position and loop forward for another pair
            }
          else if(arr[i] == Y)
          {
              while( j < n && arr[j] != X)
                j++;

              if(j < n && arr[j] == X)
              min_dist = min(min_dist,abs(i-j));
            i = j;
          }
          else
           i++;
        }
        System.out.println(min_dist);
    }
}
6
3 5 4 2 5 5 
3 5
1

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n) hara n massivin ölçüsüdür. Burada bəzilərindən istifadə edirik döngə zamanı maksimum n dəfə işləyən, bizi xətti zaman mürəkkəbliyinə aparır.

Kosmik Mürəkkəblik

O (1) çünki burada köməkçi yerdən istifadə etmirik.

References

Translate »