Ən Uzun Artıran Nəticənin İnşası (N log N)

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Amazon BankBazaar Paytm Samsung
Geyim İkili axtarış Dinamik proqramlaşdırmaBaxılıb 72

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

Sizə verilir array of tamsayılar. “Ən uzun artan ardıcıllığın inşası (N log N)” problemi, ən uzun artan ardıcıllığın qurulmasını xahiş edir.

misal

arr[]={1, 4, 7, 2, 9, 6, 12, 3 }
12, 9, 7, 4, 1 and the size of this longest increasing subsequence is 5.

Izahat

Bir massivdə artan ən uzun ardıcıllığı tapırıq.

Ən Uzun Artıran Nəticənin İnşası (N log N)Pin

Ən uzun artan ardıcıllığın qurulması alqoritmi (N log N)

1. Create two arrays lastIndexes and firstIndexes of size n, and initialize both of the arrays with 0 and -1 respectively.
2. Traverse the array from 1 to n(length of the array).
  1. Check if the current array element is less than the arr[lastIndexes[0]], if true, then update lastIndexes[0]=1.
  2. Check if the arr[i] is greater than the arr[lastIndexes[leng-1]], do the following
    1. Set the firstIndexes[i] to lastIndexes[leng-1].
    2. lastIndexes[leng++] = i.
  3. Else get the position of arr[i] using binary search and do the following.
    1. Update the value at firstIndexes[i] to lastIndexes[position-1].
    2. Update the value of the lastIndexes[position] to i.
3. Print the array, by initializing the value of i to the firstIndexes[i].

Izahat

Bir sıra tamsayı verdik və qurmağı xahiş etdik ən uzun artan ardıcıllıq. Bunun üçün biz iki massivi istifadə edəcəyik lastIndexes və firstIndexes və müvafiq olaraq 0 və -1 dəyəri ilə dolduracağıq. firstIndexes massivi 1 olaraq başlanacaqdır. Çünki bu dəyərləri indeks olaraq mövqelər kimi saxlayacaqdır. Dizini gəzərkən dəyərləri yeniləyəcəyik.

Dizini 1-dən n-ə qədər keçəcəyik. Harada n - massivin uzunluğu. Keçirərkən lastIndexes massivi bir sıra mövqeyi və ya indeksi kimi istifadə ediləcəkdir. Mövcud massiv elementinin lastIndexes [leng-1] massivindən az olub olmadığını yoxlamağımız üçün bəzi şərtləri yoxlayacağıq. Uzunluq əvvəlcə 1 olaraq təyin olunur, yəni heç olmasa 1 uzunluğun ardıcıllığına sahib olacağıq. Beləliklə, yuxarıdakı şərt doğrudursa, lastIndexes-i [0] 1-ə yeniləyin.

[İ] dizisinin lastIndexes [n-1] massivindən böyük olub olmadığını yoxlamalıyıq. Sonra hər iki massivi də yeniləyin, firstIndexes [i] -i lastIndexes [n-1] və lastIndexes [leng] -in son qiymətinə qoyun və leng dəyərini artırın. Əks halda cari massiv elementinin vəziyyətini öyrənməliyik. Bunun üçün ikili axtarışdan istifadə edəcəyik və bu indeksi mövqeyə gətirəcəyik. Və lastIndexes [position-1] dəyərini firstIndexes [i] və lastIndexes [position] i ilə yeniləyin.

Keçiddən sonra serialı çap etməliyik. Bunun üçün sondan 0-a keçəcəyikth hər keçiddən sonra hər bir göstəricini firstIndexes [i] vəziyyətinə gətirmək və işə salmaq və massivin hər mümkün dəyərini çap etmək.

Kodu

Ən uzun artan nəticənin inşası üçün C ++ kodu (N log N)

#include<iostream>
#include<vector>

using namespace std;

int GetPosition(int arr[], vector<int>& T, int left, int right,int key)
{
    while (right - left > 1)
    {
        int mid = left + (right - left) / 2;
        if (arr[T[mid]] >= key)
            right = mid;
        else
            left = mid;
    }
    return right;
}
int LongestIncreasingSubsequence(int arr[], int n)
{
    vector<int> lastIndexes(n, 0);
    vector<int> firstIndexes(n, -1);

    int len = 1;
    for (int i = 1; i < n; i++)
    {
        if (arr[i] < arr[lastIndexes[0]])
        {
            lastIndexes[0] = i;
        }
        else if (arr[i] > arr[lastIndexes[len - 1]])
        {
            firstIndexes[i] = lastIndexes[len - 1];
            lastIndexes[len++] = i;
        }
        else
        {
            int positon = GetPosition(arr, lastIndexes, -1, len - 1, arr[i]);
            firstIndexes[i] = lastIndexes[positon - 1];
            lastIndexes[positon] = i;
        }
    }
    cout << "Longest Increase Subsequence:" << endl;
    for (int i = lastIndexes[len - 1]; i >= 0; i = firstIndexes[i])
        cout << arr[i] << " ";
    cout << endl;

    cout<<"LIS size:\n";

    return len;
}
int main()
{
    int arr[] = { 1, 4, 7, 2, 9, 6, 12, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);

    cout<< LongestIncreasingSubsequence(arr, n);

    return 0;
}
Longest Increase Subsequence:
12 9 7 4 1
LIS size:
5

Ən Uzun Artıran Nəticənin İnşası üçün Java kodu (N log N)

import java.util.Arrays;

class LongestIncreasingSubsequence
{
    public static int GetPosition(int arr[], int T[], int left, int right, int key)
    {
        while (right - left > 1)
        {
            int mid = left + (right - left) / 2;
            if (arr[T[mid]] >= key)
                right = mid;
            else
                left = mid;
        }
        return right;
    }
    public static int getSubsequence(int arr[], int n)
    {
        int lastIndexes[] = new int[n];

        Arrays.fill(lastIndexes, 0);

        int firstIndexes[] = new int[n];

        Arrays.fill(firstIndexes, -1);

        int len = 1;

        for (int i = 1; i < n; i++)
        {
            if (arr[i] < arr[lastIndexes[0]])
                lastIndexes[0] = i;
            else if (arr[i] > arr[lastIndexes[len - 1]])
            {
                firstIndexes[i] = lastIndexes[len - 1];
                lastIndexes[len++] = i;
            }
            else
            {
                int positon = GetPosition(arr, lastIndexes, -1, len - 1, arr[i]);
                firstIndexes[i] = lastIndexes[positon - 1];
                lastIndexes[positon] = i;
            }
        }
        System.out.println("Longest Increasing Subsequence of given input");
        for (int i = lastIndexes[len - 1]; i >= 0; i = firstIndexes[i])
            System.out.print(arr[i] + " ");

        System.out.println();

        return len;
    }
    public static void main(String[] args)
    {
        int arr[] = { 1, 4, 7, 2, 9, 6, 12, 3 };
        int n = arr.length;

        System.out.print("LIS size:\n" + getSubsequence(arr, n)+"\n");
    }
}
Longest Increasing Subsequence of given input
12 9 7 4 1
LIS size:
5

 

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n log n) burada “n” massivdəki elementlərin sayıdır. Bizə loqaritmik amil verən ikili axtarışdan istifadə etdiyimiz üçün. Ancaq hər bir indeks üçün ikili axtarışa ehtiyacımız olsa. O zaman ən pis vəziyyətdə zaman karmaşıklığı O (N log N) olacaqdır.

Kosmik Mürəkkəblik

O (n) burada “n” massivdəki elementlərin sayıdır. FirstIndexes və lastIndexes kimi iki müvəqqəti massiv yaratdıq. Kosmik mürəkkəblik olur O (N).

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