logo

TechCodeview

Sorterad efterföljd av storlek 3 i linjär tid med konstant utrymme

Givet en array är uppgiften att hitta tre element i denna array så att de är i sorterad form, dvs. för alla tre element a[i] a[j] och a[k] följer de detta förhållande: a[i]< a[j] < a[k] där i< j < k . Detta problem måste lösas med hjälp av konstant utrymme eller inget extra utrymme.

Detta problem är redan löst i linjär tid med hjälp av linjärt rymd: Hitta en sorterad delsekvens av storlek 3 i linjär tid

Exempel:  



  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

Lösning: Målet är att hitta tre element a b och c sådan att a< b < c och elementen måste förekomma i samma sekvens i arrayen.

Närma sig: Uppgiften handlar om att hitta tre element a b c där 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 (små) bör lagra det minsta elementet i arrayen och den andra variabeln stor kommer att tilldelas ett värde när det redan finns ett mindre värde i (små) variabel. Detta kommer att leda till bildandet av ett par av två variabler som kommer att bilda de två första elementen i den nödvändiga sekvensen. På liknande sätt om ett annat värde kan hittas i arrayen som tilldelas när de två första variablerna redan är tilldelade och har ett mindre värde än det nuvarande elementet, skulle sökningen efter det tredje värdet vara komplett. Detta avslutar tripletten a b och c så att a< b < c in similar sequence to the array.

Algoritm  

  1. Skapa tre variabler små - Lagrar det minsta elementet stor - lagrar det andra elementet i sekvensen i - loopräknare
  2. Flytta längs inmatningsfältet från början till slut.
  3. Om det aktuella elementet är mindre än eller lika med variabeln små uppdatera variabeln.
  4. Annars om det aktuella elementet är mindre än eller lika med variabeln stor uppdatera variabeln. Så här får vi ett par (liten stor) var i detta ögonblick små< large och de inträffar i önskad sekvens.
  5. Annars om de två föregående fallen inte matchar, bryt slingan eftersom vi har ett par där det nuvarande elementet är större än båda variablerna små och stor . Lagra index i variabel i .
  6. Om paussatsen inte har påträffats är det garanterat att det inte finns någon sådan triplett.
  7. Annars finns det en triplett som uppfyller kriterierna men variabeln små kan ha uppdaterats till ett nytt mindre värde.
  8. Så Traversera arrayen från start till index i.
  9. Tilldela om variabeln små till något element mindre än stor det är garanterat att det finns en.
  10. Skriv ut värdena små stor och arrayelementet

Genomförande :

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>

Produktion 
5 7 8

Komplexitetsanalys:  

    Tidskomplexitet: O(n). 
    Eftersom arrayen endast korsas dubbelt så är tidskomplexiteten O(2*n) som är lika med På) .Rymdkomplexitet: O(1). 
    Eftersom endast tre element lagras är rymdkomplexiteten konstant eller O(1) .