Намерете сортирана подпоследователност с размер 3 за линейно време  


Ниво на трудност M
Често задавани в Avalara Capital One Цитадела Citrix иБей Fab 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 цяло число. Поискахме да разберем сортирано подпоследователност в дадения масив. Сортираната подпоследователност съдържа три числа, които трябва да намерим в сортиран ред и трябва да бъде последователно, не непрекъснато, а последователно, първото число трябва да е по-малко от второто число, а второто число да е по-малко от третото число, и първо, второто и третото трябва да се подредят.

Вижте също
Пренаредете масива така, че четните елементи на индекса да са по-малки, а нечетните елементи на индекса да са по-големи

Ще прекосим масива от 1 до по-малко от n, ще оставим първия и последния елемент на индекса, както е. Защото сме маркирали тези -1 в двата масива, които създадохме, малки и страхотни. Маркирахме техния първи и индексният елемент е равен на -1 съответно на малки и големи масиви. Преминаване на масива и проверка дали arr [i] е по-малко или равно на arr [минимум], където минимумът сме маркирали като 0, ако условието е установено, че е вярно, след това актуализирайте стойността на minimum до i и маркирате текущия малък масив елемент до -1.

Същото нещо, което ще направим с големия масив, но с от обхождането на масива от втория елемент от дясната страна до 0. Ще прекосим масива и ще проверим дали arr [i] е по-голям или равен на arr [максимум ], ако е вярно, тогава трябва да актуализираме стойността максимум до 0 и велик [i] до -1. В противен случай ще поставим максимума като велик [i]. След това отново ще прекосим масива и ще проверим дали small [i] и great [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

Java код за намиране на сортирана подпоследователност с размер 3 за линейно време

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

Анализ на сложността  

Сложност във времето

О (п) където "н" е броят на елементите в масива. Преминахме през всички елементи на масива. И тъй като размерът на масива е N. Времевата сложност също е линейна.

Вижте също
Премахване на дубликати от сортиран масив

Сложност на пространството

О (п) където "н" е броят на елементите в масива. Съхраняваме по-малкия и по-големия елемент за всеки елемент от масив. Така космическата сложност също е линейна.