logo

TechCodeview

Posortowany podciąg o rozmiarze 3 w czasie liniowym przy użyciu stałej przestrzeni

Mając daną tablicę, zadaniem jest znalezienie trzech elementów tej tablicy w taki sposób, aby były one posortowane, tj. dla dowolnych trzech elementów a[i] a[j] i a[k] podlegają następującej zależności: a[ja]< a[j] < a[k] Gdzie I< j < k . Ten problem należy rozwiązać za pomocą stała przestrzeń lub brak dodatkowej przestrzeni.

Problem ten został już rozwiązany w czasie liniowym przy użyciu przestrzeni liniowej: Znajdź posortowany podciąg o rozmiarze 3 w czasie liniowym

Przykłady:  



  Input:   arr[] = {12 11 10 5 2 6 30}   Output:   5 6 30 or 2 6 30   Explanation:   Answer is 5 6 30 because 5 < 6 < 30 and they occur in this sequence in the array.   Input:   arr[] = {5 7 4 8}   Output:   5 7 8   Explanation:   Answer is 5 7 8 because 5 < 7 < 8 and they occur in the same sequence in the array

Rozwiązanie: Celem jest znalezienie trzech elementów a b i c takie, że A< b < c a elementy muszą występować w tej samej kolejności w tablicy.

Zbliżać się: Problem polega na znalezieniu trzech elementów a b c, gdzie a< b < c and they must appear in the same order as in the array. So the intuition at any step must be followed as such. One of the variable (mały) powinien przechowywać najmniejszy element tablicy i drugą zmienną duży zostanie przypisana wartość, gdy w pliku istnieje już mniejsza wartość (mały) zmienny. Doprowadzi to do powstania pary dwóch zmiennych, które utworzą pierwsze dwa elementy wymaganego ciągu. Podobnie, jeśli w tablicy przypisanej, gdy przypisano już dwie pierwsze zmienne, można znaleźć inną wartość, która ma mniejszą wartość niż bieżący element, wyszukiwanie trzeciej wartości zostanie zakończone. To kończy trójkę a b i c w taki sposób, że a< b < c in similar sequence to the array.

Algorytm  

  1. Utwórz trzy zmienne mały - Przechowuje najmniejszy element duży - przechowuje drugi element sekwencji I - licznik pętli
  2. Poruszaj się po tablicy wejściowej od początku do końca.
  3. Jeśli obecny element jest mniejszy lub równy zmiennej mały zaktualizować zmienną.
  4. Inaczej, jeśli obecny element jest mniejszy lub równy zmiennej duży zaktualizować zmienną. Mamy więc parę (mały duży) w tym momencie, gdzie mały< large i występują one w wymaganej kolejności.
  5. W przeciwnym razie, jeśli poprzednie dwa przypadki nie pasują, przerwij pętlę, ponieważ mamy parę, w której obecny element jest większy niż obie zmienne mały I duży . Zapisz indeks w zmiennej I .
  6. Jeśli nie napotkano instrukcji break, gwarantuje się, że taka trójka nie istnieje.
  7. W przeciwnym razie istnieje trójka spełniająca kryteria, ale zmienna mały mogła zostać zaktualizowana do nowej, mniejszej wartości.
  8. Zatem przejdź przez tablicę od początku do indeksu i.
  9. Przypisz ponownie zmienną mały do dowolnego elementu mniejszego niż duży mamy pewność, że taki istnieje.
  10. Wydrukuj wartości mały duży i element tablicy

Realizacja :

C++ 
// C/C++ program to find a sorted sub-sequence of // size 3 using constant space #include    using namespace std; // A function to fund a sorted sub-sequence of size 3 void find3Numbers(int arr[] int n) {  // Initializing small and large(second smaller)  // by INT_MAX  int small = INT_MAX large = INT_MAX;  int i;  for (i = 0; i < n; i++)  {  // Update small for smallest value of array  if (arr[i] <= small)  small = arr[i];  // Update large for second smallest value of  // array after occurrence of small  else if (arr[i] <= large)  large = arr[i];  // If we reach here we found 3 numbers in  // increasing order : small large and arr[i]  else  break;  }  if (i == n)  {  printf('No such triplet found');  return;  }  // last and second last will be same but first  // element can be updated retrieving first element  // by looping upto i  for (int j = 0; j <= i; j++)  {  if (arr[j] < large)  {  small = arr[j];  break;  }  }  printf('%d %d %d' small large arr[i]);  return; } // Driver program to test above function int main() {  int arr[] = {5 7 4 8};  int n = sizeof(arr)/sizeof(arr[0]);  find3Numbers(arr n);  return 0; }
Java 
// Java program to find a sorted subsequence of // size 3 using constant space class GFG {  // A function to fund a sorted subsequence of size 3  static void find3Numbers(int arr[] int n)  {  // Initializing small and large(second smaller)  // by INT_MAX  int small = +2147483647 large = +2147483647;  int i;  for (i = 0; i < n; i++)  {  // Update small for smallest value of array  if (arr[i] <= small)  small = arr[i];    // Update large for second smallest value of  // array after occurrence of small  else if (arr[i] <= large)  large = arr[i];    // If we reach here we found 3 numbers in  // increasing order : small large and arr[i]  else  break;  }    if (i == n)  {  System.out.print('No such triplet found');  return;  }    // last and second last will be same but first  // element can be updated retrieving first element  // by looping upto i  for (int j = 0; j <= i; j++)  {  if (arr[j] < large)  {  small = arr[j];  break;  }  }    System.out.print(small+' '+large+' '+arr[i]);  return;  }    // Driver program  public static void main(String arg[])  {  int arr[] = {5 7 4 8};  int n = arr.length;  find3Numbers(arr n);  } } // This code is contributed by Anant Agarwal.
Python3 
# Python3 program to find a sorted subsequence  # of size 3 using constant space # Function to fund a sorted subsequence of size 3 def find3Numbers(arr n): # Initializing small and large(second smaller) # by INT_MAX small = +2147483647 large = +2147483647 for i in range(n): # Update small for smallest value of array if (arr[i] <= small): small = arr[i] # Update large for second smallest value of # array after occurrence of small elif (arr[i] <= large): large = arr[i] # If we reach here we found 3 numbers in # increasing order : small large and arr[i] else: break if (i == n): print('No such triplet found') return # last and second last will be same but # first element can be updated retrieving  # first element by looping upto i for j in range(i + 1): if (arr[j] < large): small = arr[j] break print(small' 'large' 'arr[i]) return # Driver program arr= [5 7 4 8] n = len(arr) find3Numbers(arr n) # This code is contributed by Anant Agarwal.
C# 
// C# program to find a sorted sub-sequence of // size 3 using constant space using System; class GFG {    // A function to fund a sorted sub-sequence  // of size 3  static void find3Numbers(int []arr int n)  {    // Initializing small and large(second smaller)  // by INT_MAX  int small = +2147483647 large = +2147483647;  int i;  for (i = 0; i < n; i++)  {    // Update small for smallest value of array  if (arr[i] <= small)  small = arr[i];    // Update large for second smallest value of  // array after occurrence of small  else if (arr[i] <= large)  large = arr[i];    // If we reach here we found 3 numbers in  // increasing order : small large and arr[i]  else  break;  }    if (i == n)  {  Console.Write('No such triplet found');  return;  }    // last and second last will be same but first  // element can be updated retrieving first element  // by looping upto i  for (int j = 0; j <= i; j++)  {  if (arr[j] < large)  {  small = arr[j];  break;  }  }    Console.Write(small + ' ' + large + ' ' + arr[i]);  return;  }    // Driver program  public static void Main()  {  int []arr = {5 7 4 8};  int n = arr.Length;  find3Numbers(arr n);  } } <br> // This code is contributed by nitin mittal
PHP 
 // PHP program to find a sorted  // subsequence of size 3 using  // constant space // A function to fund a sorted // subsequence of size 3 function find3Numbers($arr $n) { // Initializing small and  // large(second smaller) // by INT_MAX $small = PHP_INT_MAX; $large = PHP_INT_MAX; $i; for($i = 0; $i < $n; $i++) { // Update small for smallest // value of array if ($arr[$i] <= $small) $small = $arr[$i]; // Update large for second // smallest value of after  // occurrence of small else if ($arr[$i] <= $large) $large = $arr[$i]; // If we reach here we  // found 3 numbers in // increasing order :  // small large and arr[i] else break; } if ($i == $n) { echo 'No such triplet found'; return; } // last and second last will // be same but first // element can be updated  // retrieving first element // by looping upto i for($j = 0; $j <= $i; $j++) { if ($arr[$j] < $large) { $small = $arr[$j]; break; } } echo $small' ' $large' ' $arr[$i]; return; } // Driver Code $arr = array(5 7 4 8); $n = count($arr); find3Numbers($arr $n); // This code is contributed by anuj_67. ?>
JavaScript 
<script>  // JavaScript program to find a  // sorted sub-sequence of  // size 3 using constant space    // A function to fund a sorted sub-sequence  // of size 3  function find3Numbers(arr n)  {    // Initializing small and large(second smaller)  // by INT_MAX  let small = +2147483647 large = +2147483647;  let i;  for (i = 0; i < n; i++)  {    // Update small for smallest value of array  if (arr[i] <= small)  small = arr[i];    // Update large for second smallest value of  // array after occurrence of small  else if (arr[i] <= large)  large = arr[i];    // If we reach here we found 3 numbers in  // increasing order : small large and arr[i]  else  break;  }    if (i == n)  {  document.write('No such triplet found');  return;  }    // last and second last will be same but first  // element can be updated retrieving first element  // by looping upto i  for (let j = 0; j <= i; j++)  {  if (arr[j] < large)  {  small = arr[j];  break;  }  }    document.write(small + ' ' + large + ' ' + arr[i]);  return;  }    let arr = [5 7 4 8];  let n = arr.length;  find3Numbers(arr n);   </script>

Wyjście 
5 7 8

Analiza złożoności:  

    Złożoność czasowa: O(n). 
    Ponieważ tablica jest przemierzana tylko dwukrotnie, złożoność czasowa jest większa O(2*n) co jest równe NA) .Złożoność przestrzeni: O(1). 
    Ponieważ przechowywane są tylko trzy elementy, złożoność przestrzeni jest stała lub O(1) .