logo

TechCodeview

Sortirani podniz veličine 3 u linearnom vremenu pomoću konstantnog prostora

S obzirom na niz, zadatak je pronaći tri elementa tog niza tako da su u sortiranom obliku, tj. za bilo koja tri elementa a[i] a[j] i a[k] slijede ovaj odnos: a[i]< a[j] < a[k] gdje ja< j < k . Ovaj se problem mora riješiti korištenjem stalni prostor ili bez dodatnog prostora.

Ovaj problem je već riješen u linearnom vremenu koristeći linearni prostor: Pronađite sortirani podniz veličine 3 u linearnom vremenu

strojni jezik

Primjeri:  



  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

Otopina: Cilj je pronaći tri elementa a b i c takav da a< b < c a elementi se moraju pojaviti u istom nizu u nizu.

Pristup: Problem se bavi pronalaženjem tri elementa a b c gdje je 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 (mali) treba pohraniti najmanji element niza i drugu varijablu velika će se dodijeliti vrijednost kada već postoji manja vrijednost prisutna u (mali) varijabla. To će dovesti do formiranja para od dvije varijable koje će činiti prva dva elementa traženog niza. Slično, ako se druga vrijednost može pronaći u nizu koji je dodijeljen kada su prve dvije varijable već dodijeljene i ima manju vrijednost od sadašnjeg elementa, potraga za trećom vrijednošću bila bi dovršena. Ovo dovršava triplet a b i c tako da je a< b < c in similar sequence to the array.

str u int

Algoritam  

  1. Napravite tri varijable mali - Pohranjuje najmanji element velika - pohranjuje drugi element niza ja - brojač petlji
  2. Krećite se nizom unosa od početka do kraja.
  3. Ako je sadašnji element manji ili jednak varijabli mali ažurirajte varijablu.
  4. Inače ako je sadašnji element manji ili jednak varijabli velika ažurirajte varijablu. Dakle, ovdje imamo par (mali veliki) u ovom trenutku gdje mali< large a javljaju se traženim redoslijedom.
  5. Inače, ako se prethodna dva slučaja ne podudaraju, prekinuti petlju jer imamo par gdje je sadašnji element veći od obje varijable mali i velika . Pohranite indeks u varijablu ja .
  6. Ako naredba break nije naišla, tada je zajamčeno da takav triplet ne postoji.
  7. Inače postoji trojka koja zadovoljava kriterije osim varijable mali možda je ažuriran na novu manju vrijednost.
  8. Dakle, prijeđite nizom od početka do indeksa i.
  9. Ponovno dodijelite varijablu mali na bilo koji element manji od velika zajamčeno je da postoji.
  10. Ispišite vrijednosti mali velika i i-ti element niza

Provedba :

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>

Izlaz 
5 7 8

Analiza složenosti:  

    Vremenska složenost: O(n). 
    Budući da se nizom prolazi samo dva puta, veća je vremenska složenost O(2*n) koji je jednak Na) .Složenost prostora: O(1). 
    Budući da su samo tri elementa pohranjena složenost prostora je konstantna ili O(1) .