Dado um array, a tarefa é encontrar três elementos deste array de modo que eles estejam em forma ordenada, ou seja, para quaisquer três elementos a[i], a[j] e a[k] eles seguem este relacionamento: um[eu]< a[j] < a[k] onde eu< j < k . Este problema deve ser resolvido usando espaço constante ou nenhum espaço extra.
Este problema já foi resolvido em tempo linear usando espaço linear: Encontre uma subsequência classificada de tamanho 3 em tempo linear
lista de látex
Exemplos:
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 Solução: O objetivo é encontrar três elementos um b ec tal que um< b < c e os elementos devem ocorrer na mesma sequência na matriz.
Abordagem: O problema trata de encontrar três elementos a b c onde 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 (pequeno) deve armazenar o menor elemento do array e a segunda variável grande será atribuído um valor quando já houver um valor menor presente no (pequeno) variável. Isto levará à formação de um par de duas variáveis que formarão os dois primeiros elementos da sequência necessária. Da mesma forma, se outro valor puder ser encontrado na matriz que é atribuído quando as duas primeiras variáveis já estão atribuídas e tem um valor menor que o elemento atual, a busca pelo terceiro valor será concluída. Isso completa o trio a b e c tal que a< b < c in similar sequence to the array.
como converter int em string
Algoritmo
- Crie três variáveis pequeno - Armazena o menor elemento grande - armazena o segundo elemento da sequência eu - contador de loops
- Mova-se ao longo da matriz de entrada do início ao fim.
- Se o elemento presente for menor ou igual à variável pequeno atualize a variável.
- Caso contrário, se o elemento presente for menor ou igual à variável grande atualize a variável. Então aqui temos um par (pequeno grande) neste instante onde pequeno< large e eles ocorrem na sequência necessária.
- Caso contrário, se os dois casos anteriores não corresponderem, interrompa o loop, pois temos um par onde o elemento presente é maior que ambas as variáveis pequeno e grande . Armazene o índice na variável eu .
- Se a instrução break não for encontrada, é garantido que tal trio não existe.
- Caso contrário, há um trio que satisfaz os critérios, mas a variável pequeno pode ter sido atualizado para um novo valor menor.
- Portanto, percorra a matriz do início ao índice i.
- Reatribuir a variável pequeno para qualquer elemento menor que grande é garantido que existe um.
- Imprima os valores pequeno grande e i-ésimo elemento da matriz
Implementação :
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>
Saída
5 7 8
Análise de Complexidade:
Como a matriz é percorrida apenas duas vezes, a complexidade do tempo é O(2*n) que é igual a Sobre) .
Como apenas três elementos são armazenados, a complexidade do espaço é constante ou O(1) .