Сызықтық уақыттағы 3 өлшемді сұрыпталған тізбекті табыңыз


Күрделілік дәрежесі орта
Жиі кіреді Авалара Capital One Цитадель Citrix еВау Фаб Synopsys
Array

Проблемалық мәлімдеме

«Сызықтық уақыттағы 3 өлшемді сұрыпталған тізбекті табу» мәселесінде сізде бүтін сан массив. Проблемалық есеп үш санды [i] <массив [k] <массив [k], ал i <j <k болатындай етіп табуды сұрайды.

мысал

arr[] = {11,34,2,5,1,7,4 }
2 5 7

Түсіндіру

2-ден 5-ке, ал 5-тен 7-ге, ал олардың индекстері бір-бірінен аз болатындай етіп.

Алгоритм

1. Declare a new array “small” and “great” of size as same as the original array.
2. Set the value of maximum to n-1, and the value of minimum to 0.
3. Marked the first element of the array we created to -1.
4. Traverse the array from i=1 to less than n(n is the length of the array).
  1. Check if arr[i] is smaller or equal to arr[minimum], if true
    1. Set minimum to i and small[i] to -1.
  2. Else put small[i] = minimum.
5. Traverse the array from i=n-2 to less than equal to 0(n is the length of the array).
  1. Check if arr[i] is greater than or equal to arr[maximum], if true
    1. Set maximum to i and great[i] to -1.
  2. Else put great[i] = maximum.
6. Traverse the array from i=0 to n and check if small[i] and great[i] is not equal to -1, then print the arr[small[i]] , arr[i] and arr[great[i]].
  1. Return

Түсіндіру

Бізде бар массив of бүтін сан. Біз мұны анықтап беруді өтіндік сұрыпталған берілген жиымдағы тізбектілік. Сұрыпталған тізбектелген үш саннан тұрады, оларды сұрыпталған тәртіпте табу керек және ол дәйектілікпен емес, дәйекті түрде болуы керек, бірінші сан екінші саннан, екінші сан үшінші саннан кіші, ал біріншіден, екінші және үшінші ретке келуі керек.

Біз массивті n-ден 1-ге дейін өтеміз, бірінші және соңғы индекс элементін сол күйінде қалдырамыз. Біз сол -1-ді біз құрған екі массивте кішігірім және керемет етіп белгілеп қойдық. Олардың бірінші және индекс элементі сәйкесінше кіші және үлкен массивтердің -1-ге тең екенін белгіледік. Массивті айналып өтіп, [i] arr [минимумнан] аз немесе оған тең екенін тексеріңіз, мұндағы минимум біз 0 деп белгіледік, егер шарт дұрыс болса, минимум мәнін i-ге дейін жаңартыңыз, және ағымдағы кіші массивті белгілеңіз элемент -1.

Дәл сол сияқты біз үлкен массивпен, бірақ массивтің өтпесінен бастап оң жақтың екінші элементінен 0-ге дейін жасаймыз. Біз массивті айналып өтіп, [i] массивінің [максимумнан үлкен не оған тең екендігін тексереміз. ], егер бұл шын болса, онда біз максимум мәнін 0-ге, ал үлкен [i] мәнін -1-ге дейін жаңартуымыз керек. Біз максимумды керемет етіп қоямыз [i]. Осыдан кейін біз массивті тағы да айналып өтіп, кіші [i] және үлкен [i] -1-ге тең еместігін тексереміз, егер ол шын болса, онда көрсетілген мәндерді басып шығарамыз.

Сызықтық уақыттағы 3 өлшемді сұрыпталған тізбекті табыңыз

 

код

C ++ коды, сызықтық уақытта 3 өлшемді сұрыпталған тізбекті табу

#include<iostream>
using namespace std;

void getTriplet(int arr[], int n)
{
    int maximum = n - 1;
    int minimum = 0;
    int i;

    int* small = new int[n];

    small[0] = -1;
    for (i = 1; i < n; i++)
    {
        if (arr[i] <= arr[minimum])
        {
            minimum = i;
            small[i] = -1;
        }
        else
            small[i] = minimum;
    }

    int* great = new int[n];

    great[n - 1] = -1;
    for (i = n - 2; i >= 0; i--)
    {
        if (arr[i] >= arr[maximum])
        {
            maximum = i;
            great[i] = -1;
        }
        else
            great[i] = maximum;
    }

    for (i = 0; i < n; i++)
    {
        if (small[i] != -1 && great[i] != -1)
        {
            cout << arr[small[i]] << " " << arr[i] << " "<< arr[great[i]];
            return;
        }
    }

    cout << "3 numbers not found";

    delete[] small;
    delete[] great;

    return;
}
int main()
{
    int arr[] = { 11,34,2,5,1,7,4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    getTriplet(arr, n);
    return 0;
}
2 5 7

Сызықтық уақыттағы 3 өлшемді сұрыпталған ізін табу үшін Java коды

class SortedSubsequenceSize3
{
    public static void getTriplet(int arr[])
    {
        int n = arr.length;
        int maximum = n - 1;

        int minimum = 0;
        int i;

        int[] small = new int[n];

        small[0] = -1;
        for (i = 1; i < n; i++)
        {
            if (arr[i] <= arr[minimum])
            {
                minimum = i;
                small[i] = -1;
            }
            else
                small[i] = minimum;
        }
        int[] great = new int[n];

        great[n - 1] = -1;
        for (i = n - 2; i >= 0; i--)
        {
            if (arr[i] >= arr[maximum])
            {
                maximum = i;
                great[i] = -1;
            }
            else
                great[i] = maximum;
        }
        for (i = 0; i < n; i++)
        {
            if (small[i] != -1 && great[i] != -1)
            {
                System.out.println(arr[small[i]] + " " + arr[i] + " " + arr[great[i]]);
                return;
            }
        }
        System.out.println("3 numbers not found");
        return;
    }
    public static void main(String[] args)
    {
        int arr[] = { 11,34,2,5,1,7,4 };
        getTriplet(arr);
    }
}
2 5 7

Күрделілікті талдау

Уақыттың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны. Біз массивтің барлық элементтерін араладық. Массивтің өлшемі N болғандықтан, уақыттың күрделілігі де сызықтық болып табылады.

Ғарыштың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны. Біз массивтің әрбір элементі үшін кішірек және үлкен элементті сақтадық. Сонымен, ғарыштық қиындықтар да сызықтық болып табылады.