სწორხაზოვან დროში იპოვნეთ დაზუსტებული ზომის 3


Რთული ტური საშუალო
ხშირად ეკითხებიან ავალარა Capital One ციხედ Citrix eBay Fab ანოტაცია
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, თუ პირობა აღმოჩნდა ჭეშმარიტი, შემდეგ განაახლეთ მინიმუმის მნიშვნელობა i- ზე და მონიშნეთ მიმდინარე მცირე მასივი ელემენტი -1.

იგივე უნდა გავაკეთოთ დიდი მასივის შემთხვევაში, მაგრამ მასივის გადაკვეთადან მარჯვენა მხარის მეორე ელემენტიდან 0. ჩვენ გადავკვეთთ მასივს და შეამოწმებთ arr [i] არის arr- ის მეტი ან ტოლი [მაქსიმალური ], თუ ეს სიმართლეა, ჩვენ უნდა განვაახლოთ მაქსიმუმის მნიშვნელობა 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 ზომაში სწორ დროში

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. დროის სირთულე ასევე ხაზოვანია.

სივრცის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. ჩვენ შევინახავდით უფრო და უფრო პატარა ელემენტს თითოეული მასივის ელემენტისთვის. ამრიგად, სივრცის სირთულე ასევე ხაზოვანია.