Рубрики

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

Учитывая массив из n целых чисел, найдите 3 элемента, таких что a [i] <a [j] <a [k] и i <j <k за 0 (n) времени. Если таких триплетов несколько, выведите любой из них.

Примеры:

Input:  arr[] = {12, 11, 10, 5, 6, 2, 30}
Output: 5, 6, 30

Input:  arr[] = {1, 2, 3, 4}
Output: 1, 2, 3 OR 1, 2, 4 OR 2, 3, 4

Input:  arr[] = {4, 3, 2, 1}
Output: No such triplet

Подсказка: используйте вспомогательное пространство

Решение:
1) Создайте вспомогательный массив меньшего размера [0..n-1]. меньше [i] должен хранить индекс числа, которое меньше, чем arr [i] и находится на левой стороне arr [i]. меньший [i] должен содержать -1, если такого элемента нет.
2) Создайте еще один вспомогательный массив больше [0..n-1]. больше [i] должен хранить индекс числа, которое больше, чем arr [i] и находится справа от arr [i]. Значение more [i] должно содержать -1, если такого элемента нет.
3) Наконец, пройдитесь по меньшим [] и большему [] и найдите индекс i, для которого и меньший [i], и больший [i] не равны -1.

C ++

// C ++ программа для поиска отсортированной подпоследовательности размера 3
#include <bits/stdc++.h>

using namespace std; 

  
// Функция для финансирования отсортированной подпоследовательности размера 3

void find3Numbers(int arr[], int n) 

    int max = n-1; // Индекс максимального элемента с правой стороны

    int min = 0; // Индекс минимального элемента с левой стороны

    int i; 

      

    // Создать массив, в котором будет храниться индекс меньшего

    // элемент на левой стороне. Если нет меньшего элемента

    // на левой стороне, тогда меньше [i] будет -1.

    int *smaller = new int[n]; 

    smaller[0] = -1; // первая запись всегда будет -1

    for (i = 1; i < n; i++) 

    

        if (arr[i] <= arr[min]) 

        

            min = i; 

            smaller[i] = -1; 

        

        else

            smaller[i] = min; 

    

      

    // Создать другой массив, в котором будет храниться индекс

    // больший элемент на правой стороне. Если нет больше

    // элемент на правой стороне, тогда больше [i] будет -1.

    int *greater = new int[n]; 

    greater[n-1] = -1; // последняя запись всегда будет -1

    for (i = n-2; i >= 0; i--) 

    

        if (arr[i] >= arr[max]) 

        

            max = i; 

            greater[i] = -1; 

        

        else

            greater[i] = max; 

    

      

    // Теперь найти номер, который имеет большее число на

    // правая сторона и меньшее число на левой стороне

    for (i = 0; i < n; i++) 

    

        if (smaller[i] != -1 && greater[i] != -1) 

        

            cout << arr[smaller[i]] << " " << arr[i] << " " << arr[greater[i]]; 

            return

        

    

      

    // Если мы достигнем числа, то таких 3-х чисел нет

    cout << "No such triplet found"

      

    // Освобождаем динамически распределяемую память, чтобы избежать утечки памяти

    delete [] smaller; 

    delete [] greater; 

      

    return

  
// Код драйвера

int main() 

    int arr[] = {12, 11, 10, 5, 6, 2, 30}; 

    int n = sizeof(arr)/sizeof(arr[0]); 

    find3Numbers(arr, n); 

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

// C программа для поиска отсортированной подпоследовательности размера 3
#include<stdio.h>

  
// Функция для финансирования отсортированной подпоследовательности размера 3

void find3Numbers(int arr[], int n)

{

   int max = n-1; // Индекс максимального элемента с правой стороны

   int min = 0; // Индекс минимального элемента с левой стороны

   int i;

  

   // Создать массив, в котором будет храниться индекс меньшего

   // элемент на левой стороне. Если нет меньшего элемента

   // на левой стороне, тогда меньше [i] будет -1.

   int *smaller = new int[n];

   smaller[0] = -1;  // первая запись всегда будет -1

   for (i = 1; i < n; i++)

   {

       if (arr[i] <= arr[min])

       {

          min = i;

          smaller[i] = -1;

       }

       else

          smaller[i] = min;

   }

  

   // Создать другой массив, в котором будет храниться индекс

   // больший элемент на правой стороне. Если нет больше

   // элемент на правой стороне, тогда больше [i] будет -1.

   int *greater = new int[n];

   greater[n-1] = -1;  // последняя запись всегда будет -1

   for (i = n-2; i >= 0; i--)

   {

       if (arr[i] >= arr[max])

       {

          max = i;

          greater[i] = -1;

       }

       else

          greater[i] = max;

   }

  

   // Теперь найти номер, который имеет большее число на

   // правая сторона и меньшее число на левой стороне

   for (i = 0; i < n; i++)

   {

       if (smaller[i] != -1 && greater[i] != -1)

       {

          printf("%d %d %d", arr[smaller[i]],

                 arr[i], arr[greater[i]]);

          return;

       }

   }

  

   // Если мы достигнем числа, то таких 3-х чисел нет

   printf("No such triplet found");

  

   // Освобождаем динамически распределяемую память, чтобы избежать утечки памяти

   delete [] smaller;

   delete [] greater;

  

   return;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int arr[] = {12, 11, 10, 5, 6, 2, 30};

    int n = sizeof(arr)/sizeof(arr[0]);

    find3Numbers(arr, n);

    return 0;

}

Джава

// Java-программа для поиска отсортированной подпоследовательности размера 3

import java.io.*;

  

class SortedSubsequence

{

    // Функция для поиска отсортированной подпоследовательности размера 3

    static void find3Numbers(int arr[])

    {

        int n = arr.length;

        int max = n-1; // Индекс максимального элемента с правой стороны

        int min = 0; // Индекс минимального элемента с левой стороны

        int i;

  

        // Создать массив, в котором будет храниться индекс меньшего

        // элемент на левой стороне. Если нет меньшего элемента

        // на левой стороне, тогда меньше [i] будет -1.

        int[] smaller = new int[n];

        smaller[0] = -1// первая запись всегда будет -1

        for (i = 1; i < n; i++)

        {

            if (arr[i] <= arr[min])

            {

                min = i;

                smaller[i] = -1;

            }

            else

                smaller[i] = min;

        }

  

        // Создать другой массив, в котором будет храниться индекс

        // больший элемент на правой стороне. Если нет больше

        // элемент на правой стороне, тогда больше [i] будет -1.

        int[] greater = new int[n];

        greater[n-1] = -1// последняя запись всегда будет -1

        for (i = n-2; i >= 0; i--)

        {

            if (arr[i] >= arr[max])

            {

                max = i;

                greater[i] = -1;

            }

            else

                greater[i] = max;

        }

  

        // Теперь найти номер, который имеет большее число

        // справа и меньшее число слева

        for (i = 0; i < n; i++)

        {

            if (smaller[i] != -1 && greater[i] != -1)

            {

                System.out.print(arr[smaller[i]]+" "+

                                 arr[i]+" "+ arr[greater[i]]);

                return;

            }

        }

  

        // Если мы достигнем числа, то таких 3-х чисел нет

        System.out.println("No such triplet found");

        return;

    }

  

    public static void main (String[] args)

    {

        int arr[] = {12, 11, 10, 5, 6, 2, 30};

        find3Numbers(arr);

    }

}
/ * Этот код предоставлен Девешом Агравалом * /

питон

# Программа Pythion для финансирования отсортированной подпоследовательности размера 3

  

def find3numbers(arr):

    n = len(arr)

    max = n-1 # Индекс максимального элемента с правой стороны

    min = 0 # Индекс минимального элемента с левой стороны

  

    # Создать массив, в котором будет храниться индекс меньшего

    # элемент на левой стороне. Если нет меньшего элемента

    # слева, тогда меньше [i] будет -1.

    smaller = [0]*10000

    smaller[0] = -1

    for i in range(1,n):

        if (arr[i] <= arr[min]):

            min = i

            smaller[i] = -1

        else:

            smaller[i] = min

  

    # Создайте другой массив, который будет хранить индекс

    # больший элемент на правой стороне. Если нет больше

    Элемент # справа, тогда больше [i] будет -1.

    greater = [0]*10000

    greater[n-1] = -1

  

    for i in range(n-2,-1,-1):

        if (arr[i] >= arr[max]):

            max = i

            greater[i] = -1

  

        else:

            greater[i] = max

  

    # Теперь найдите номер, который имеет большее число на

    # правая сторона и меньшее число на левой стороне

    for i in range(0,n):

        if smaller[i] != -1 and greater[i] != -1:

            print arr[smaller[i]], arr[i], arr[greater[i]]

            return

  

    # Если мы доберемся сюда, то таких 3 цифр нет

    print "No triplet found"

    return

  

  
# Функция драйвера для проверки вышеуказанной функции

arr = [12, 11, 10, 5, 6, 2, 30]

find3numbers(arr)

  
# Этот код предоставлен Девешом Агравалом

C #

// C # программа для поиска отсортированного
// подпоследовательность размера 3

using System;

  

class SortedSubsequence {

      

    // Функция для поиска отсортированного

    // подпоследовательность размера 3

    static void find3Numbers(int[] arr)

    {

        int n = arr.Length;

          

        // Индекс максимального элемента с правой стороны

        int max = n - 1; 

          

        // Индекс минимального элемента с левой стороны

        int min = 0; 

        int i;

  

        // Создать массив для хранения индекса

        // меньшего элемента на левой стороне.

        // Если нет меньшего элемента

        // на левой стороне, тогда меньше [i] будет -1.

        int[] smaller = new int[n];

          

        // первая запись всегда будет -1

        smaller[0] = -1; 

        for (i = 1; i < n; i++) {

            if (arr[i] <= arr[min]) {

                min = i;

                smaller[i] = -1;

            }

            else

                smaller[i] = min;

        }

  

        // Создать другой массив, который будет хранить

        // индекс большего элемента с правой стороны.

        // Если нет большего элемента на

        // правая сторона, тогда больше [i] будет -1.

        int[] greater = new int[n];

          

        // последняя запись всегда будет -1

        greater[n - 1] = -1; 

        for (i = n - 2; i >= 0; i--) {

            if (arr[i] >= arr[max]) {

                max = i;

                greater[i] = -1;

            }

            else

                greater[i] = max;

        }

  

        // Теперь найти номер, который имеет большее число

        // справа и меньшее число слева

        for (i = 0; i < n; i++) {

            if (smaller[i] != -1 && greater[i] != -1) {

                Console.Write(arr[smaller[i]] + " "

                     arr[i] + " " + arr[greater[i]]);

                return;

            }

        }

  

        // Если мы достигнем числа, то таких 3-х чисел нет

        Console.Write("No such triplet found");

        return;

    }

      

    // Код драйвера

    public static void Main()

    {

        int[] arr = { 12, 11, 10, 5, 6, 2, 30 };

        find3Numbers(arr);

    }

}

  
/ * Этот код предоставлен vt_m * /

PHP

<?php 
// PHP программа для поиска отсортированного
// подпоследовательность размера 3

  
// Функция для финансирования отсортированного
// подпоследовательность размера 3

function find3Numbers(&$arr, $n)

{

    $max = $n - 1; // Индекс максимального элемента

                   // с правой стороны

    $min = 0; // Индекс минимального элемента

              // с левой стороны

      

    // Создать массив, который будет хранить

    // индекс меньшего элемента на

    // левая сторона. Если не меньше

    // элемент слева

    // меньше [i] будет -1.

    $smaller = array_fill(0, $n, NULL);

    $smaller[0] = -1; // первая запись будет

                      // всегда будет -1

    for ($i = 1; $i < $n; $i++)

    {

        if ($arr[$i] <= $arr[$min])

        {

            $min = $i;

            $smaller[$i] = -1;

        }

        else

            $smaller[$i] = $min;

    }

      

    // Создать другой массив, который будет

    // сохранить индекс большего элемента

    // на правой стороне. Если нет

    // больший элемент на правой стороне,

    // тогда больше [i] будет -1.

    $greater = array_fill(0, $n, NULL);

      

    // последняя запись всегда будет -1

    $greater[$n - 1] = -1; 

    for ($i = $n - 2; $i >= 0; $i--)

    {

        if ($arr[$i] >= $arr[$max])

        {

            $max = $i;

            $greater[$i] = -1;

        }

        else

            $greater[$i] = $max;

    }

      

    // Теперь найти номер, который имеет оба

    // большее число справа

    // и меньшее число слева

    for ($i = 0; $i < $n; $i++)

    {

        if ($smaller[$i] != -1 && 

            $greater[$i] != -1)

        {

            echo $arr[$smaller[$i]]." ".

                      $arr[$i] . " "

                      $arr[$greater[$i]];

            return;

        }

    }

      

    // Если мы достигнем числа, то там

    // нет таких 3 чисел

    printf("No such triplet found");

      

    return;

}

  
// Код драйвера

$arr = array(12, 11, 10, 5, 6, 2, 30);

$n = sizeof($arr);

find3Numbers($arr, $n);

  
// Этот код добавлен
// ChitraNayal
?>

Выход:

5 6 30 

Сложность времени: O (n)
Вспомогательное пространство: O (n)

Источник: Как найти 3 числа в порядке возрастания и увеличения индексов в массиве за линейное время

Упражнение:
1. Найдите подпоследовательность размера 3 такую, что arr [i] arr [k].
2. Найдите отсортированную подпоследовательность размера 4 в линейном времени

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

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

0.00 (0%) 0 votes