logo

TechCodeview

Sortierte Teilfolge der Größe 3 in linearer Zeit unter Verwendung konstanten Raums

Bei einem gegebenen Array besteht die Aufgabe darin, drei Elemente dieses Arrays so zu finden, dass sie in sortierter Form vorliegen, d. h. für alle drei Elemente a[i], a[j] und a[k] folgen sie dieser Beziehung: ein[ich]< a[j] < a[k] Wo ich< j < k . Dieses Problem muss mit gelöst werden konstanter Raum oder kein zusätzlicher Platz.

Dieses Problem ist bereits in linearer Zeit unter Verwendung des linearen Raums gelöst: Finden Sie eine sortierte Teilsequenz der Größe 3 in linearer Zeit

Beispiele:  



  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ösung: Ziel ist es, drei Elemente zu finden ein b und c so dass A< b < c und die Elemente müssen in der gleichen Reihenfolge im Array vorkommen.

Ansatz: Das Problem besteht darin, drei Elemente a b c zu finden, wobei 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 (klein) sollte das kleinste Element des Arrays und die zweite Variable speichern groß wird ein Wert zugewiesen, wenn bereits ein kleinerer Wert vorhanden ist (klein) Variable. Dies führt zur Bildung eines Paars aus zwei Variablen, die die ersten beiden Elemente der erforderlichen Sequenz bilden. Ebenso wäre die Suche nach dem dritten Wert abgeschlossen, wenn in dem zugewiesenen Array ein anderer Wert gefunden werden kann, der zugewiesen wurde, während die ersten beiden Variablen bereits zugewiesen wurden, und der einen kleineren Wert als das aktuelle Element aufweist. Dies vervollständigt das Triplett a b und c so, dass a< b < c in similar sequence to the array.

Algorithmus  

  1. Erstellen Sie drei Variablen klein - Speichert das kleinste Element groß - speichert das zweite Element der Sequenz ich - Schleifenzähler
  2. Bewegen Sie sich vom Anfang bis zum Ende entlang des Eingabearrays.
  3. Wenn das aktuelle Element kleiner oder gleich der Variable ist klein Aktualisieren Sie die Variable.
  4. Andernfalls, wenn das aktuelle Element kleiner oder gleich der Variable ist groß Aktualisieren Sie die Variable. Hier bekommen wir also ein Paar (klein groß) in diesem Moment wo klein< large und sie treten in der erforderlichen Reihenfolge auf.
  5. Andernfalls unterbrechen Sie die Schleife, wenn die beiden vorherigen Fälle nicht übereinstimmen, da wir ein Paar haben, bei dem das aktuelle Element größer als beide Variablen ist klein Und groß . Speichern Sie den Index in einer Variablen ich .
  6. Wenn die break-Anweisung nicht angetroffen wurde, ist garantiert, dass kein solches Triplett vorhanden ist.
  7. Andernfalls erfüllt ein Triplett die Kriterien, aber die Variable klein wurde möglicherweise auf einen neuen, kleineren Wert aktualisiert.
  8. Durchlaufen Sie also das Array vom Start bis zum Index i.
  9. Weisen Sie die Variable neu zu klein zu jedem Element kleiner als groß es ist garantiert, dass es einen gibt.
  10. Drucken Sie die Werte aus klein groß und i-tes Array-Element

Durchführung :

int in String umwandeln
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>

Ausgabe 
5 7 8

Komplexitätsanalyse:  

    Zeitkomplexität: O(n). 
    Da das Array nur doppelt so lang durchlaufen wird, ist die Zeitkomplexität höher O(2*n) was gleich ist An) .Raumkomplexität: O(1). 
    Da nur drei Elemente gespeichert werden, ist die Raumkomplexität konstant oder O(1) .