Birinci və ikinci kiçik elementləri tapın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon MAQ o9 həlləri TCS
Geyim AxtarışBaxılıb 1038

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

Tapdığımız birinci və ikinci ən kiçik elementləri problemi array tam ədədi. Bir sıra içərisində birinci və ikinci ən kiçik tam ədədləri tapın və ya bir sıra içərisində ən kiçik iki ədədi tapın.

misal

Input

7, 6, 8, 10, 11, 5, 13, 99

Buraxılış

Birincisi Kiçik 5, İkincisi Kiçik 6-dır

Burada bu problemin həlli üçün çox yanaşmalarımız var, ancaq bunlardan yalnız ikisini müzakirə edirik. İstədiyiniz nəticəni tapmaq üçün təkrarlamadan istifadə edirik və birinci və ikinci minimum dəyərləri saxlayırıq.

Birinci və ikinci kiçik elementləri tapmaq üçün yanaşma 1

Alqoritm

1. Ən kiçik və sonrakı ən kiçik iki dəyişəni götürün.
2. Deyək ki, ən kiçiyi massivin birinci elementi ilə başlandı.
3. Array dəyərlərini müqayisə etməyə davam edin:
a. Əgər massiv elementi ən kiçikdən kiçikdirsə

  • Ən kiçik dəyərini nextSmallest dəyəri ilə müqayisə edin və müvafiq olaraq yeniləyin.
  • Ən kiçik dəyəri yeniləyin.

b. Başqa bir şey müqayisə etsin ki, massiv elementi ən kiçikdən böyük, lakin nextSmallest-dən kiçikdirsə, onda nextSmallest dəyişəninin dəyərini dəyişdirin.

Həyata keçirilməsi

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 small,next_small=INT_MAX;
  small = arr[0]; 
  for(int i=1;i<N;i++)
  {
    if(arr[i] < small)
    {
      next_small = small;
      small = arr[i];  
    }      
    else if(arr[i] < next_small and arr[i] > small)
      next_small = arr[i];
  }  
  cout << "Smallest and the second smallest numbers are respectively "<< small << " and " << next_small <<endl;
  return 0;
}

Java Proqramı

import java.util.Scanner;
class sum
{
    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 small,next_small=10000000;
        small = arr[0];
        for(int i=1;i<n;i++)
        {
          if(arr[i] < small)
          {
            next_small = small;
            small = arr[i];  
          }      
          else if(arr[i] < next_small && arr[i] > small)
            next_small = arr[i];
        }
        System.out.println("Smallest and the second smallest numbers are respectively "+small+ " and "+next_small);
    }
}
8
4 1 8 9 11 3 77 2
Smallest and the second smallest numbers are respectively 1 and 2

Birinci və İkinci Ən kiçik elementləri tapmaq üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi: O (N), burada N - massivdə mövcud olan elementlərin sayı. Burada yalnız 1 dəq və ikinci min elementlərini bütün massivdə təkrarlayarkən saxlayırıq.

Kosmik Mürəkkəblik: O (1), çünki bizi yalnız O (1) məkan mürəkkəbliyinə aparan bəzi dəyişənlərdən istifadə edirik.

Birinci və ikinci kiçik elementləri tapmaq üçün yanaşma 2

Alqoritm

1. Birləşdirmə və ya Heap sortundan istifadə edərək sıranı sıralamaq kifayətdir. Sort () STL-dən də istifadə edə bilərik.
2. Birinci və ikinci element artan sırada olduğu kimi sırasıyla ən kiçik və sonrakı ən kiçik olacaq.

Həyata keçirilməsi

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];
  //sort the array and the first two elements are the desired values
  sort(arr,arr+N);
  cout << "Smallest and the second smallest numbers are respectively "<< arr[0] << " and  " << arr[1] <<endl;
  return 0;
}

Java Proqramı

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    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();
        }
        Arrays.sort(arr);
        System.out.println("Smallest and the second smallest numbers are respectively "+arr[0]+ " and "+arr[1]);
    }
}
5
1 5 3 2 9
Smallest and the second smallest numbers are respectively 1 and 2

Birinci və İkinci Ən kiçik elementləri tapmaq üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi: O (NlogN), burada N - massivdəki elementlərin sayı. Burada O (n * logn) zaman mürəkkəbliyi olan inbuild sort funksiyasından istifadə edirik.
Kosmik Mürəkkəblik: O (1), çünki burada heç bir köməkçi yer istifadə etmirik. Sadəcə verilən massivin sayını dəyişdiririk.

References

Crack Sistemi Dizayn Müsahibələri
Translate »