Verilmiş massivdə sabit nöqtəni tapın

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Verilmiş bir array n fərqli elementdən, müəyyən bir nöqtədə sabit bir nöqtə tapın, burada sabit bir nöqtə element dəyərinin indekslə eyni olduğunu göstərir.

misal

Input

5

arr [] = {0,4,8,2,9}

Buraxılış

0 bu massivdə sabit bir nöqtədir, çünki dəyər və indeks hər ikisi də 0-a bərabərdir.

Input

6

arr [] = {2,7,9,3,10,8}

Buraxılış

3 bu massivdə sabit bir nöqtədir, çünki dəyər 3, indeks isə 3-dür.

Yanaşma 1 (xətti axtarış)

Budur biz keçmək massivin başlanğıcından sonuna qədər və sabit nöqtənin şərtini yoxlayın və şərt doğrudursa, elementi yazdırın, əks halda “No fixed point in the array".

Alqoritm

1. Hər element üçün massivin sonuna qədər
2. element dəyərinin indeks dəyəri ilə eyni olub olmadığını yoxlayın, elementi doğrudursa.

Həyata keçirilməsi

Verilmiş bir massivdə sabit nöqtə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];
  }
  for(int i = 0; i < N; i++)
    {
      if(arr[i] == i)
        {
          cout<<arr[i]<<endl;
          return 0;
        }
    }
  cout<<"No fixed point in the array \n";
  return 0;
}

import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int temp=0;
        for(int i=0;i<n;i++)
        {
          if(a[i] == i)
            {
              System.out.println(a[i]);
              temp=1;
              i=n;
            }
        }
        if(temp==1)
        System.out.println("No fixed point in the array \n");
    }
}

5
1 2 1 3 5

3

Yanaşma 2 (ikili axtarış)

Bu vəziyyətdə, bu yanaşmanı sıralanmış sıra üçün istifadə edə bilərik. Müraciət edin ikili axtarış və sabit bir nöqtə üçün vəziyyəti yoxlayın. Əgər belə bir mövqe tapsanız, o elementi yazdırın, əks halda “Dizidə sabit nöqtə yoxdur” yazdırın.

Alqoritm

1. Aşağı və yüksək dəyişənləri massivin başlanğıcına və sonuna təyin edin
2. Aşağıya qədər yüksəkdən azdır.
3. Əvvəlcə orta elementin sabit bir nöqtə olub olmadığını yoxlayın, bəli, orta elementi yazdırın.
   a. orta element dəyəri orta indeksdən azdırsa. Varsa, aşağı +1 ortalarına qədər yeniləyin
   b. orta element dəyəri orta indeksdən böyükdürsə. Varsa, yüksək səviyyənin ortasına qədər yeniləyin

Həyata keçirilməsi

Verilmiş bir massivdə sabit nöqtəni tapmaq üçün C ++ proqramı

#include <bits/stdc++.h>
using namespace std;
int bin_search_fixed(int arr[],int low , int high)
{
  while(low <= high)
  {
    int mid = low + (high - low)/2;
    
    if(arr[mid] == mid)
      return mid;
    
    else if(arr[mid] < mid)
      low = mid +1;
    else
    high = mid - 1;  
    
  }
return -1;
}
int main()
{
  int N;
  cin>>N;
  int arr[N];
  for(int i=0;i<N;i++)
  {
      cin>>arr[i];
  }
  int index = bin_search_fixed(arr,0,N-1);
  if(index >= 0)
    cout << arr[index]<<endl;
    
  else
    cout<<"No fixed point in the array \n";
  
  return 0;
}

import java.util.Scanner;
class sum
{
    public static int bin_search_fixed(int arr[],int low , int high)
    {
      while(low <= high)
      {
        int mid = low + (high - low)/2;

        if(arr[mid] == mid)
          return mid;

        else if(arr[mid] < mid)
          low = mid +1;
        else
        high = mid - 1;  

      }
    return -1;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int index = bin_search_fixed(a,0,n-1);
        if(index >= 0)
          System.out.println(a[index]);
        else
          System.out.println("No fixed point in the array");
    }
}

5
1 2 1 6 5

No fixed point in the array