Classifique as posições pares em ordem crescente e as posições ímpares em ordem decrescente
Recebemos uma matriz de n números distintos. A tarefa é classificar todos os números pares em ordem crescente e os números ímpares em ordem decrescente. A matriz modificada deve conter todos os números pares classificados, seguidos por números ímpares classificados inversamente.
Observe que o primeiro elemento é considerado uniforme devido ao seu índice 0.
Exemplos:
Entrada: arr[] = {0 1 2 3 4 5 6 7}
Saída: arr[] = {0 2 4 6 7 5 3 1}
Explicação:
Elementos pares: 0 2 4 6
Elementos de lugares ímpares: 1 3 5 7
Coloque os elementos pares em ordem crescente:
0 2 4 6
Elementos de lugar ímpar em ordem decrescente:
7 5 3 1
Entrada: arr[] = {3 1 2 4 5 9 13 14 12}
Saída: {2 3 5 12 13 14 9 4 1}
Explicação:
Elementos pares: 3 2 5 13 12
Elementos de lugares ímpares: 1 4 9 14
Coloque os elementos pares em ordem crescente:
2 3 5 12 13
Elementos de lugar ímpar em ordem decrescente:
14 9 4 1
[Abordagem Naive] - O(n Log n) Tempo e O(n) Espaço
A ideia é simples. Criamos dois arrays auxiliares evenArr[] e oddArr[] respectivamente. Percorremos a matriz de entrada e colocamos todos os elementos pares em EvenArr[] e os elementos ímpares em oddArr[]. Em seguida, classificamos EvenArr[] em ordem crescente e oddArr[] em ordem decrescente. Por fim, copie evenArr[] e oddArr[] para obter o resultado necessário.
C++ // Program to separately sort even-placed and odd // placed numbers and place them together in sorted // array. #include using namespace std ; void bitonicGenerator ( vector < int >& arr ) { // create evenArr[] and oddArr[] vector < int > evenArr ; vector < int > oddArr ; // Put elements in oddArr[] and evenArr[] as // per their position for ( int i = 0 ; i < arr . size (); i ++ ) { if ( ! ( i % 2 )) evenArr . push_back ( arr [ i ]); else oddArr . push_back ( arr [ i ]); } // sort evenArr[] in ascending order // sort oddArr[] in descending order sort ( evenArr . begin () evenArr . end ()); sort ( oddArr . begin () oddArr . end () greater < int > ()); int i = 0 ; for ( int j = 0 ; j < evenArr . size (); j ++ ) arr [ i ++ ] = evenArr [ j ]; for ( int j = 0 ; j < oddArr . size (); j ++ ) arr [ i ++ ] = oddArr [ j ]; } // Driver Program int main () { vector < int > arr = { 1 5 8 9 6 7 3 4 2 0 }; bitonicGenerator ( arr ); for ( int i = 0 ; i < arr . size (); i ++ ) cout < < arr [ i ] < < ' ' ; return 0 ; }
Java // Program to separately sort even-placed and odd // placed numbers and place them together in sorted // array. import java.util.* ; public class Main { public static void bitonicGenerator ( int [] arr ) { // create evenArr[] and oddArr[] List < Integer > evenArr = new ArrayList <> (); List < Integer > oddArr = new ArrayList <> (); // Put elements in oddArr[] and evenArr[] as // per their position for ( int i = 0 ; i < arr . length ; i ++ ) { if ( i % 2 == 0 ) evenArr . add ( arr [ i ] ); else oddArr . add ( arr [ i ] ); } // sort evenArr[] in ascending order // sort oddArr[] in descending order Collections . sort ( evenArr ); Collections . sort ( oddArr Collections . reverseOrder ()); int i = 0 ; for ( int num : evenArr ) arr [ i ++] = num ; for ( int num : oddArr ) arr [ i ++] = num ; } public static void main ( String [] args ) { int [] arr = { 1 5 8 9 6 7 3 4 2 0 }; bitonicGenerator ( arr ); for ( int num : arr ) System . out . print ( num + ' ' ); } }
Python # Program to separately sort even-placed and odd # placed numbers and place them together in sorted # array. def bitonic_generator ( arr ): # create evenArr[] and oddArr[] evenArr = [] oddArr = [] # Put elements in oddArr[] and evenArr[] as # per their position for i in range ( len ( arr )): if i % 2 == 0 : evenArr . append ( arr [ i ]) else : oddArr . append ( arr [ i ]) # sort evenArr[] in ascending order # sort oddArr[] in descending order evenArr . sort () oddArr . sort ( reverse = True ) i = 0 for num in evenArr : arr [ i ] = num i += 1 for num in oddArr : arr [ i ] = num i += 1 # Driver Program arr = [ 1 5 8 9 6 7 3 4 2 0 ] bitonic_generator ( arr ) print ( ' ' . join ( map ( str arr )))
C# // Program to separately sort even-placed and odd // placed numbers and place them together in sorted // array. using System ; using System.Collections.Generic ; using System.Linq ; class Program { static void BitonicGenerator ( int [] arr ) { // create evenArr[] and oddArr[] List < int > evenArr = new List < int > (); List < int > oddArr = new List < int > (); // Put elements in oddArr[] and evenArr[] as // per their position for ( int i = 0 ; i < arr . Length ; i ++ ) { if ( i % 2 == 0 ) evenArr . Add ( arr [ i ]); else oddArr . Add ( arr [ i ]); } // sort evenArr[] in ascending order // sort oddArr[] in descending order evenArr . Sort (); oddArr . Sort (( a b ) => b . CompareTo ( a )); int index = 0 ; foreach ( var num in evenArr ) arr [ index ++ ] = num ; foreach ( var num in oddArr ) arr [ index ++ ] = num ; } static void Main () { int [] arr = { 1 5 8 9 6 7 3 4 2 0 }; BitonicGenerator ( arr ); Console . WriteLine ( string . Join ( ' ' arr )); } }
JavaScript // Program to separately sort even-placed and odd // placed numbers and place them together in sorted // array. function bitonicGenerator ( arr ) { // create evenArr[] and oddArr[] const evenArr = []; const oddArr = []; // Put elements in oddArr[] and evenArr[] as // per their position for ( let i = 0 ; i < arr . length ; i ++ ) { if ( i % 2 === 0 ) evenArr . push ( arr [ i ]); else oddArr . push ( arr [ i ]); } // sort evenArr[] in ascending order // sort oddArr[] in descending order evenArr . sort (( a b ) => a - b ); oddArr . sort (( a b ) => b - a ); let i = 0 ; for ( const num of evenArr ) arr [ i ++ ] = num ; for ( const num of oddArr ) arr [ i ++ ] = num ; } // Driver Program const arr = [ 1 5 8 9 6 7 3 4 2 0 ]; bitonicGenerator ( arr ); console . log ( arr . join ( ' ' ));
PHP // Program to separately sort even-placed and odd // placed numbers and place them together in sorted // array. function bitonicGenerator(&$arr) { // create evenArr[] and oddArr[] $evenArr = []; $oddArr = []; // Put elements in oddArr[] and evenArr[] as // per their position foreach ($arr as $i => $value) { if ($i % 2 === 0) $evenArr[] = $value; else $oddArr[] = $value; } // sort evenArr[] in ascending order // sort oddArr[] in descending order sort($evenArr); rsort($oddArr); $i = 0; foreach ($evenArr as $num) { $arr[$i++] = $num; } foreach ($oddArr as $num) { $arr[$i++] = $num; } } // Driver Program $arr = [1 5 8 9 6 7 3 4 2 0]; bitonicGenerator($arr); echo implode(' ' $arr);
Saída
1 2 3 6 8 9 7 5 4 0
[Abordagem Esperada - 1] - O(n Log n) Tempo e O(1) Espaço
O problema também pode ser resolvido sem a utilização de espaço Auxiliar. A ideia é trocar as posições ímpares do índice da primeira metade pelas posições pares do índice da segunda metade e, em seguida, classificar a matriz da primeira metade em ordem crescente e a segunda metade da matriz em ordem decrescente.
C++ #include using namespace std ; void bitonicGenerator ( vector < int >& arr ) { // first odd index int i = 1 ; // last index int n = arr . size (); int j = n - 1 ; // if last index is odd if ( j % 2 != 0 ) // decrement j to even index j -- ; // swapping till half of array while ( i < j ) { swap ( arr [ i ] arr [ j ]); i += 2 ; j -= 2 ; } // Sort first half in increasing sort ( arr . begin () arr . begin () + ( n + 1 ) / 2 ); // Sort second half in decreasing sort ( arr . begin () + ( n + 1 ) / 2 arr . end () greater < int > ()); } // Driver Program int main () { vector < int > arr = { 1 5 8 9 6 7 3 4 2 0 }; bitonicGenerator ( arr ); for ( int i = 0 ; i < arr . size (); i ++ ) cout < < arr [ i ] < < ' ' ; return 0 ; }
Java import java.util.Arrays ; class BitonicGenerator { public static void bitonicGenerator ( int [] arr ) { // first odd index int i = 1 ; // last index int n = arr . length ; int j = n - 1 ; // if last index is odd if ( j % 2 != 0 ) // decrement j to even index j -- ; // swapping till half of array while ( i < j ) { int temp = arr [ i ] ; arr [ i ] = arr [ j ] ; arr [ j ] = temp ; i += 2 ; j -= 2 ; } // Sort first half in increasing order Arrays . sort ( arr 0 ( n + 1 ) / 2 ); // Sort second half in decreasing order Arrays . sort ( arr ( n + 1 ) / 2 n ); reverse ( arr ( n + 1 ) / 2 n ); } private static void reverse ( int [] arr int start int end ) { end -- ; while ( start < end ) { int temp = arr [ start ] ; arr [ start ] = arr [ end ] ; arr [ end ] = temp ; start ++ ; end -- ; } } // Driver Program public static void main ( String [] args ) { int [] arr = { 1 5 8 9 6 7 3 4 2 0 }; bitonicGenerator ( arr ); for ( int num : arr ) { System . out . print ( num + ' ' ); } } }
Python def bitonic_generator ( arr ): # first odd index i = 1 # last index n = len ( arr ) j = n - 1 # if last index is odd if j % 2 != 0 : # decrement j to even index j -= 1 # swapping till half of array while i < j : arr [ i ] arr [ j ] = arr [ j ] arr [ i ] i += 2 j -= 2 # Sort first half in increasing arr [:( n + 1 ) // 2 ] = sorted ( arr [:( n + 1 ) // 2 ]) # Sort second half in decreasing arr [( n + 1 ) // 2 :] = sorted ( arr [( n + 1 ) // 2 :] reverse = True ) # Driver Program arr = [ 1 5 8 9 6 7 3 4 2 0 ] bitonic_generator ( arr ) print ( ' ' . join ( map ( str arr )))
C# // Function to generate a bitonic sequence using System ; using System.Collections.Generic ; using System.Linq ; class Program { static void BitonicGenerator ( List < int > arr ) { // first odd index int i = 1 ; // last index int n = arr . Count ; int j = n - 1 ; // if last index is odd if ( j % 2 != 0 ) // decrement j to even index j -- ; // swapping till half of array while ( i < j ) { int temp = arr [ i ]; arr [ i ] = arr [ j ]; arr [ j ] = temp ; i += 2 ; j -= 2 ; } // Sort first half in increasing arr . Sort ( 0 ( n + 1 ) / 2 ); // Sort second half in decreasing arr . Sort (( n + 1 ) / 2 n - ( n + 1 ) / 2 Comparer < int > . Create (( x y ) => y . CompareTo ( x ))); } // Driver Program static void Main () { List < int > arr = new List < int > { 1 5 8 9 6 7 3 4 2 0 }; BitonicGenerator ( arr ); Console . WriteLine ( string . Join ( ' ' arr )); } }
JavaScript // Function to generate a bitonic sequence function bitonicGenerator ( arr ) { // first odd index let i = 1 ; // last index let n = arr . length ; let j = n - 1 ; // if last index is odd if ( j % 2 !== 0 ) // decrement j to even index j -- ; // swapping till half of array while ( i < j ) { [ arr [ i ] arr [ j ]] = [ arr [ j ] arr [ i ]]; i += 2 ; j -= 2 ; } // Sort first half in increasing arr . sort (( a b ) => a - b ); // Sort second half in decreasing arr . slice (( n + 1 ) / 2 ). sort (( a b ) => b - a ); } // Driver Program let arr = [ 1 5 8 9 6 7 3 4 2 0 ]; bitonicGenerator ( arr ); console . log ( arr . join ( ' ' ));
Saída
1 2 3 6 8 9 7 5 4 0
Nota: Os códigos Python e JS acima parecem exigir espaço extra. Deixe-nos saber nos comentários sobre seus pensamentos e quaisquer implementações alternativas.
[Abordagem Esperada - 2] - O(n Log n) Tempo e O(1) Espaço
Outra abordagem eficiente para resolver o problema no espaço auxiliar O(1) é por Usando multiplicação negativa .
As etapas envolvidas são as seguintes:
- Multiplique todos os elementos no índice par por -1.
- Classifique todo o array. Desta forma, podemos obter todos os índices pares no início, pois agora são números negativos.
- Agora reverta o sinal desses elementos.
- Depois disso, inverta a primeira metade da matriz que contém um número par para colocá-lo em ordem crescente.
- E então inverta a metade restante da matriz para formar números ímpares em ordem decrescente.
Observação: Este método só é aplicável se todos os elementos da matriz forem não negativos.
Um exemplo ilustrativo da abordagem acima:
Deixe dada matriz: arr[] = {0 1 2 3 4 5 6 7}
Matriz após multiplicar por -1 para elementos pares: arr[] = {0 1 -2 3 -4 5 -6 7}
Array após classificação: arr[] = {-6 -4 -2 0 1 3 5 7}
Matriz após reverter valores negativos: arr[] = {6 4 2 0 1 3 5 7}
Depois de reverter a primeira metade do array: arr[] = {0 2 4 6 1 3 5 7}
Depois de reverter a segunda metade do array: arr[] = {0 2 4 6 7 5 3 1}
Abaixo está o código para a abordagem acima:
C++ #include using namespace std ; void bitonicGenerator ( vector < int >& arr ) { // Making all even placed index // element negative for ( int i = 0 ; i < arr . size (); i ++ ) { if ( i % 2 == 0 ) arr [ i ] = -1 * arr [ i ]; } // Sorting the whole array sort ( arr . begin () arr . end ()); // Finding the middle value of // the array int mid = ( arr . size () - 1 ) / 2 ; // Reverting the changed sign for ( int i = 0 ; i <= mid ; i ++ ) { arr [ i ] = -1 * arr [ i ]; } // Reverse first half of array reverse ( arr . begin () arr . begin () + mid + 1 ); // Reverse second half of array reverse ( arr . begin () + mid + 1 arr . end ()); } // Driver Program int main () { vector < int > arr = { 1 5 8 9 6 7 3 4 2 0 }; bitonicGenerator ( arr ); for ( int i = 0 ; i < arr . size (); i ++ ) cout < < arr [ i ] < < ' ' ; return 0 ; }
Java import java.util.Arrays ; import java.util.List ; public class BitonicGenerator { public static void bitonicGenerator ( List < Integer > arr ) { // Making all even placed index // element negative for ( int i = 0 ; i < arr . size (); i ++ ) { if ( i % 2 == 0 ) arr . set ( i - 1 * arr . get ( i )); } // Sorting the whole array Collections . sort ( arr ); // Finding the middle value of // the array int mid = ( arr . size () - 1 ) / 2 ; // Reverting the changed sign for ( int i = 0 ; i <= mid ; i ++ ) { arr . set ( i - 1 * arr . get ( i )); } // Reverse first half of array Collections . reverse ( arr . subList ( 0 mid + 1 )); // Reverse second half of array Collections . reverse ( arr . subList ( mid + 1 arr . size ())); } // Driver Program public static void main ( String [] args ) { List < Integer > arr = Arrays . asList ( 1 5 8 9 6 7 3 4 2 0 ); bitonicGenerator ( arr ); for ( int i : arr ) System . out . print ( i + ' ' ); } }
Python def bitonic_generator ( arr ): # Making all even placed index # element negative for i in range ( len ( arr )): if i % 2 == 0 : arr [ i ] = - 1 * arr [ i ] # Sorting the whole array arr . sort () # Finding the middle value of # the array mid = ( len ( arr ) - 1 ) // 2 # Reverting the changed sign for i in range ( mid + 1 ): arr [ i ] = - 1 * arr [ i ] # Reverse first half of array arr [: mid + 1 ] = reversed ( arr [: mid + 1 ]) # Reverse second half of array arr [ mid + 1 :] = reversed ( arr [ mid + 1 :]) # Driver Program arr = [ 1 5 8 9 6 7 3 4 2 0 ] bitonic_generator ( arr ) print ( ' ' . join ( map ( str arr )))
C# using System ; using System.Collections.Generic ; using System.Linq ; class BitonicGenerator { public static void BitonicGeneratorMethod ( List < int > arr ) { // Making all even placed index // element negative for ( int i = 0 ; i < arr . Count ; i ++ ) { if ( i % 2 == 0 ) arr [ i ] = - 1 * arr [ i ]; } // Sorting the whole array arr . Sort (); // Finding the middle value of // the array int mid = ( arr . Count - 1 ) / 2 ; // Reverting the changed sign for ( int i = 0 ; i <= mid ; i ++ ) { arr [ i ] = - 1 * arr [ i ]; } // Reverse first half of array arr . Take ( mid + 1 ). Reverse (). ToList (). CopyTo ( arr ); // Reverse second half of array arr . Skip ( mid + 1 ). Reverse (). ToList (). CopyTo ( arr mid + 1 ); } // Driver Program public static void Main () { List < int > arr = new List < int > { 1 5 8 9 6 7 3 4 2 0 }; BitonicGeneratorMethod ( arr ); Console . WriteLine ( string . Join ( ' ' arr )); } }
JavaScript function bitonicGenerator ( arr ) { // Making all even placed index // element negative for ( let i = 0 ; i < arr . length ; i ++ ) { if ( i % 2 === 0 ) arr [ i ] = - 1 * arr [ i ]; } // Sorting the whole array arr . sort (( a b ) => a - b ); // Finding the middle value of // the array const mid = Math . floor (( arr . length - 1 ) / 2 ); // Reverting the changed sign for ( let i = 0 ; i <= mid ; i ++ ) { arr [ i ] = - 1 * arr [ i ]; } // Reverse first half of array arr . slice ( 0 mid + 1 ). reverse (). forEach (( val index ) => arr [ index ] = val ); // Reverse second half of array arr . slice ( mid + 1 ). reverse (). forEach (( val index ) => arr [ mid + 1 + index ] = val ); } // Driver Program let arr = [ 1 5 8 9 6 7 3 4 2 0 ]; bitonicGenerator ( arr ); console . log ( arr . join ( ' ' ));
Saída
1 2 3 6 8 9 7 5 4 0
Criar questionário
