logo

TechCodeview

Сортирана подпоследователност с размер 3 в линейно време с помощта на постоянно пространство

При даден масив задачата е да се намерят три елемента от този масив, така че да са в сортирана форма, т.е. за всеки три елемента a[i] a[j] и a[k] те следват тази връзка: a[i]< a[j] < a[k] където аз< j < k . Този проблем трябва да бъде решен с помощта на постоянно пространство или без допълнително пространство.

списък с методи java

Този проблем вече е решен в линейно време с помощта на линейно пространство: Намерете сортирана подпоследователност с размер 3 в линейно време

Примери:  



  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

Решение: Целта е да се намерят три елемента а б и c такова, че а< b < c и елементите трябва да се срещат в една и съща последователност в масива.

Подход: Задачата се занимава с намирането на три елемента a b c, където 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 (малък) трябва да съхранява най-малкия елемент от масива и втората променлива големи ще бъде присвоена стойност, когато вече има по-малка стойност в (малък) променлива. Това ще доведе до образуването на двойка от две променливи, които ще формират първите два елемента от необходимата последователност. По същия начин, ако може да се намери друга стойност в масива, който е присвоен, когато първите две променливи вече са присвоени и има по-малка стойност от настоящия елемент, търсенето на третата стойност ще бъде завършено. Това завършва триплета a b и c, така че a< b < c in similar sequence to the array.

java конвертира цяло число в низ

Алгоритъм  

  1. Създайте три променливи малък - Съхранява най-малкия елемент големи - съхранява втория елемент от редицата аз - брояч на цикли
  2. Придвижете се по входния масив от началото до края.
  3. Ако настоящият елемент е по-малък или равен на променлива малък актуализирайте променливата.
  4. Иначе, ако настоящият елемент е по-малък или равен на променлива големи актуализирайте променливата. Така че тук получаваме чифт (малък голям) в този момент къде малък< large и те се появяват в необходимата последователност.
  5. В противен случай, ако предишните два случая не съвпадат, прекъснете цикъла, тъй като имаме двойка, където настоящият елемент е по-голям от двете променливи малък и големи . Съхранявайте индекса в променлива i .
  6. Ако командата break не е била открита, тогава е гарантирано, че не съществува такава тройка.
  7. В противен случай има триплет, който отговаря на критериите, но променливата малък може да е актуализиран до нова по-малка стойност.
  8. Така че обходете масива от началото до индекс i.
  9. Присвоете отново променливата малък към всеки елемент по-малко от големи гарантирано е, че има такъв.
  10. Отпечатайте стойностите малък големи и i-ти елемент от масива

Внедряване :

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>

Изход 
5 7 8

Анализ на сложността:  

    Времева сложност: O(n). 
    Тъй като масивът се пресича само два пъти, времевата сложност е O(2*n) което е равно на O(n) .Космическа сложност: O(1). 
    Тъй като се съхраняват само три елемента, пространствената сложност е постоянна или О(1) .

 

пример за OS с отворен код е