Для даного масиву завдання полягає в тому, щоб знайти три елементи цього масиву так, щоб вони були у відсортованій формі, тобто для будь-яких трьох елементів a[i] a[j] і a[k] вони дотримуються цього співвідношення: a[i]< a[j] < a[k] де i< j < k . Цю проблему необхідно вирішити за допомогою постійний простір або немає додаткового місця.
різниця дат в excel
Ця задача вже розв’язана в лінійному часі з використанням лінійного простору: Знайдіть відсортовану підпослідовність розміром 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 такий, що a< 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.
диспетчер завдань linux
Алгоритм
- Створіть три змінні маленький - Зберігає найменший елемент великий - зберігає другий елемент послідовності i - лічильник циклів
- Переміщення по вхідному масиву від початку до кінця.
- Якщо поточний елемент менший або дорівнює змінній маленький оновити змінну.
- Інакше, якщо поточний елемент менший або дорівнює змінній великий оновити змінну. Отже, ми отримуємо пару (маленький великий) в цей момент де маленький< large і вони відбуваються в необхідній послідовності.
- Інакше, якщо попередні два випадки не збігаються, розірвіть цикл, оскільки ми маємо пару, де поточний елемент більший за обидві змінні маленький і великий . Зберігайте індекс у змінній i .
- Якщо оператор break не зустрічався, то гарантовано, що такий триплет не існує.
- В іншому випадку є триплет, який задовольняє критерії, але змінна маленький можливо, було оновлено до нового меншого значення.
- Отже, пройдіть масив від початку до індексу i.
- Повторно призначте змінну маленький до будь-якого елемента менше ніж великий гарантовано, що такий існує.
- Роздрукуйте значення маленький великий і i-й елемент масиву
Реалізація :
C++// C/C++ program to find a sorted sub-sequence of // size 3 using constant space #include
// 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 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# 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 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. ?> <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(2*n) що дорівнює O(n) .
Оскільки зберігаються лише три елементи, складність простору є постійною або О(1) .
bin до bcd