Сортирайте четните в нарастващ ред и нечетните в низходящ ред
Даден ни е масив от n различни числа. Задачата е да сортирате всички четни числа в нарастващ и нечетните числа в низходящ ред. Модифицираният масив трябва да съдържа всички сортирани четни числа, последвани от обратно сортирани нечетни числа.
Обърнете внимание, че първият елемент се счита за четен поради неговия индекс 0.
Примери:
вход: arr[] = {0 1 2 3 4 5 6 7}
Изход: arr[] = {0 2 4 6 7 5 3 1}
Обяснение:
Четни елементи: 0 2 4 6
Нечетни елементи: 1 3 5 7
Елементи с четно място в нарастващ ред:
0 2 4 6
Елементи с нечетни места в низходящ ред:
7 5 3 1
вход: arr[] = {3 1 2 4 5 9 13 14 12}
Изход: {2 3 5 12 13 14 9 4 1}
Обяснение:
Четни елементи: 3 2 5 13 12
Нечетни елементи: 1 4 9 14
Елементи с четно място в нарастващ ред:
2 3 5 12 13
Елементи с нечетни места в низходящ ред:
14 9 4 1
[Наивен подход] - O(n Log n) време и O(n) пространство
Идеята е проста. Създаваме два спомагателни масива съответно evenArr[] и oddArr[]. Обхождаме входния масив и поставяме всички четно разположени елементи в evenArr[] и нечетно поставени елементи в oddArr[]. След това сортираме evenArr[] във възходящ ред и oddArr[] в низходящ ред. Накрая копирайте evenArr[] и oddArr[], за да получите необходимия резултат.
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);
Изход
1 2 3 6 8 9 7 5 4 0
[Очакван подход - 1] - O(n Log n) време и O(1) пространство
Проблемът може да бъде решен и без използването на помощно пространство. Идеята е да размените първата половина на нечетните позиции на индекса с втората половина на четните позиции на индекса и след това да сортирате първата половина на масива в нарастващ ред, а втората половина на масива в низходящ ред.
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 ( ' ' ));
Изход
1 2 3 6 8 9 7 5 4 0
Забележка: Горните кодове на Python и JS изглежда изискват допълнително място. Уведомете ни в коментари за вашите мисли и всички алтернативни реализации.
[Очакван подход - 2] - O(n Log n) време и O(1) пространство
Друг ефективен подход за решаване на проблема в O(1) спомагателното пространство е чрез Използване на отрицателно умножение .
Включените стъпки са както следва:
- Умножете всички елементи с четен индекс по -1.
- Сортирайте целия масив. По този начин можем да получим всички четни поставени индекси в началото, тъй като сега те са отрицателни числа.
- Сега обърнете знака на тези елементи.
- След това обърнете първата половина на масива, който съдържа четно поставено число, за да го направите в нарастващ ред.
- И след това обърнете останалата половина на масива, за да направите нечетни числа в низходящ ред.
Забележка: Този метод е приложим само ако всички елементи в масива са неотрицателни.
Илюстративен пример за горния подход:
Нека даден масив: arr[] = {0 1 2 3 4 5 6 7}
Масив след умножение по -1 до четно поставени елементи: arr[] = {0 1 -2 3 -4 5 -6 7}
Масив след сортиране: arr[] = {-6 -4 -2 0 1 3 5 7}
Масив след връщане на отрицателни стойности: arr[] = {6 4 2 0 1 3 5 7}
След обръщане на първата половина на масива: arr[] = {0 2 4 6 1 3 5 7}
След обръщане на втората половина на масива: arr[] = {0 2 4 6 7 5 3 1}
По-долу е кодът за горния подход:
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 ( ' ' ));
Изход
1 2 3 6 8 9 7 5 4 0
Създаване на тест
