logo

TechCodeview

Razvrščeno podzaporedje velikosti 3 v linearnem času z uporabo konstantnega prostora

Za podano matriko je naloga najti tri elemente te matrike, tako da so v razvrščeni obliki, tj. za vse tri elemente a[i] a[j] in a[k] sledijo tej zvezi: a[i]< a[j] < a[k] kjer i< j < k . To težavo je treba rešiti z uporabo stalni prostor ali brez dodatnega prostora.

vadnica za javafx

Ta problem je že rešen v linearnem času z uporabo linearnega prostora: Poiščite razvrščeno podzaporedje velikosti 3 v linearnem času

Primeri:  



  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

rešitev: Cilj je najti tri elemente a b in c tako da a< b < c in elementi se morajo pojaviti v istem zaporedju v matriki.

Pristop: Problem se ukvarja z iskanjem treh elementov a b c kjer 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 (majhen) mora shraniti najmanjši element matrike in drugo spremenljivko velik bo dodeljena vrednost, ko je v elementu že prisotna manjša vrednost (majhen) spremenljivka. To bo vodilo do oblikovanja para dveh spremenljivk, ki bosta tvorili prva dva elementa zahtevanega zaporedja. Podobno, če je mogoče najti drugo vrednost v matriki, ki je dodeljena, ko sta prvi dve spremenljivki že dodeljeni in ima manjšo vrednost od trenutnega elementa, bi bilo iskanje tretje vrednosti končano. To dopolni trojček a b in c tako, da je a< b < c in similar sequence to the array.

java pretvarja celo število v niz

Algoritem  

  1. Ustvarite tri spremenljivke majhna - Shranjuje najmanjši element velik - shrani drugi element zaporedja i - števec zank
  2. Pomikajte se po vhodni matriki od začetka do konca.
  3. Če je trenutni element manjši ali enak spremenljivki majhna posodobite spremenljivko.
  4. Drugače, če je trenutni element manjši ali enak spremenljivki velik posodobite spremenljivko. Tukaj imamo torej par (majhno veliko) v tem trenutku kje majhna< large in se pojavljajo v zahtevanem zaporedju.
  5. Sicer, če se prejšnja dva primera ne ujemata, prekinite zanko, saj imamo par, kjer je trenutni element večji od obeh spremenljivk majhna in velik . Shranite indeks v spremenljivko i .
  6. Če stavek break ni bil najden, je zagotovljeno, da tak trojček ne obstaja.
  7. Sicer obstaja trojček, ki izpolnjuje merila, vendar spremenljivka majhna morda posodobljen na novo manjšo vrednost.
  8. Torej prečkajte matriko od začetka do indeksa i.
  9. Ponovno dodelite spremenljivko majhna kateremu koli elementu manj kot velik zagotovljeno je, da obstaja.
  10. Natisnite vrednosti majhna velik in i-ti element polja

Izvedba :

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>

Izhod 
5 7 8

Analiza kompleksnosti:  

    Časovna zahtevnost: O(n). 
    Ker je matrika prečkana le dvakrat, je časovna zapletenost O(2*n) kar je enako O(n) .Kompleksnost prostora: O(1). 
    Ker so shranjeni samo trije elementi je kompleksnost prostora konstantna oz O(1) .