Əvvəlcə müsbət itkin

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Akkolit Amazon Məlumat dəsti Samsung Snapdeal
GeyimBaxılıb 74

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

“İlk çatışmayan müsbət” problemi sizə n ölçülü bir [] (sıralanmış və ya çeşidlənməmiş) bir sıra verildiyini bildirir. Bu massivdə itkin olan ilk müsbət ədədi tapın.

misal

İlk Eksik MüsbətPin

a[ ] = {1, 3, -1, 8}
 2

İzahat: Diziyi sıralasaq, {-1, 1, 3, 8} əldə edirik. Mənfi ilə məşğul deyilik tamsayılar buna görə -1 / 0-nin olub olmadığının heç bir əhəmiyyəti yoxdur. Ancaq bundan sonra serialın 1-dən bir nömrəsi olub olmadığı bizi narahat edir. Beləliklə, 1 mövcuddur, sonra növbəti rəqəm 3-dür. Ancaq 2-si əskikdir. Beləliklə, bu serialda olmayan ilk müsbət tam ədədi olur.

a[ ] = {9, -1, 8, 7}
1

İzahat: Bir daha cəhd edirik cür massivi və sonra 1-dən başlayan müsbət tam ədədin olduğu yerə qədər yoxlayın. Beləliklə çeşidlədikdən sonra {-1, 7,8,9} var. Beləliklə, ilk müsbət tamın 1-də olduğunu bilirik ki, massivdə yoxdur.

Yanaşma

Çeşidləmə istifadə

Alqoritmi ilk itkin müsbət tapmaq

1. Initialize a non-empty array a[ ] of size n.
2. Initialize an integer variable min as 1 to store the smallest positive missing element.
3. Sort the given array a[ ] of size n.
4. Traverse through the array a[ ] and check if the element at the current index in array a[ ] is equal to the variable min, increment the variable min by 1.
5. Return the variable min.

Beləliklə, giriş / çıxış bölməsində yuxarıda izah olundu ki, əvvəlcə girişləri çeşidləyirdik və sonra massivdə olmayan ilk müsbət tam ədədi yoxlayırdıq. Ancaq çeşidləmə istifadə etdiyimiz üçün bu metod kifayət qədər səmərəli deyil.

Kodu

İlk çatışmayan pozitiv tapmaq üçün C ++ proqramı
#include <bits/stdc++.h> 
using namespace std; 

int missPositive(int a[], int n){ 
    int min=1;
    sort(a, a+n);
    for(int i=0; i<n; i++){
        if(a[i]==min){
            min++;
        }
    }
    return min;
}  
int main(){ 
    int a[] = {9, -1, 1, 8, 7}; 
    int n = sizeof(a)/sizeof(a[0]);
    cout<<missPositive(a, n); 
    return 0; 
} 
2
Java Proqramının ilk itkinin pozitif olduğunu tapmaq
import java.util.Arrays;
class missing{
    static int missPositive(int a[], int n){ 
        int min=1;
        Arrays.sort(a);
        for(int i=0; i<n; i++){
            if(a[i]==min){
                min++;
            }
        }
        return min;
    }
  public static void main (String[] args){
        int a[] = {9, -1, 1, 8, 7};
        int n = a.length;
        System.out.println(missPositive(a, n));
  }
}

2

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N log N) burada n - verilən bir [] massivindəki elementlərin sayı.

Kosmik Mürəkkəblik

O (N) n element saxlamaq üçün yer istifadə etdiyimiz üçün.

Səmərəli metod

Alqoritmi ilk itkin pozitivi effektiv tapmaq

1. Initialize a non-empty array a[ ] of size n.
2. Initialize two variables of integer type val and nextval to store the current element and the next element of the array respectively.
3. Traverse through the array a[ ] and check if the element at current index in array a[ ] is greater than 0 or the element at current index in array a[ ] is greater than the array size store it in val. Traverse the array until we reach an element that is already marked or could not be marked.
4. Again Traverse the array and find the first array index which is not marked and is the smallest missing number. Return index + 1.
5. Else if all the index are marked return n +1.

Beləliklə, sadəlövh yanaşmada serialı sıraladıq. Sonra cavab axtardı. Burada serialı işarələyəcəyimiz əvəzinə sıranı sıralamayacağıq. Yəni nəzərdə tutduğum işarəni qoymaqla elementləri elementin dəyərinə bərabər indeksə yerləşdirəcəyik. Beləliklə, hansının ilk itkin müsbət olduğunu yoxlaya biləcəyik.

Kodu

İlk çatışmayan pozitiv tapmaq üçün C ++ proqramı
#include <bits/stdc++.h> 
using namespace std; 

int missPositive(int a[], int n){ 
    int num, nextnum; 
    for(int i=0; i<n; i++){ 
        if ((a[i]<=0) || (a[i]>n))
            continue; 
  
        num = a[i]; 
  
        while(a[num - 1] != num) { 
            nextnum = a[num - 1]; 
            a[num - 1] = num; 
            num = nextnum; 
            if ((num<=0) || (num>n)) 
                break; 
        } 
    } 
    for(int i=0; i<n; i++) { 
        if (a[i] != i+1) { 
            return i+1; 
        } 
    } 
    return n + 1; 
}  
int main(){ 
    int a[] = {9, -1, 1, 8, 7}; 
    int n = sizeof(a)/sizeof(a[0]);
    cout<<missPositive(a, n); 
    return 0; 
}
2
Java Proqramının ilk itkinin pozitif olduğunu tapmaq
class missing{
    static int missPositive(int a[], int n){ 
        int num, nextnum; 
      
        for(int i=0; i<n; i++){ 
            if (a[i] <= 0 || a[i] > n) 
                continue; 
      
            num = a[i]; 
      
            while(a[num - 1] != num) { 
                nextnum = a[num - 1]; 
                a[num - 1] = num; 
                num = nextnum; 
                if (num <= 0 || num > n) 
                    break; 
            } 
        } 
      
        for(int i=0; i<n; i++) { 
            if (a[i] != i+1) { 
                return i+1; 
            } 
        } 
        return n + 1; 
    }  
  public static void main (String[] args){
    int a[] = {9, -1, 1, 8, 7}; 
    int n = a.length;
    System.out.println(missPositive(a, n));
  }
}
2

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N) burada n - verilən bir [] massivindəki elementlərin sayı.

Kosmik Mürəkkəblik

O (1) çünki daimi əlavə yer istifadə edirdik.

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