偶数の場合は昇順に、奇数の場合は降順に並べ替えます
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) 空間
考え方はシンプルです。 2 つの補助配列、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 つの効率的なアプローチは次のとおりです。 負の乗算を使用する 。
必要な手順は次のとおりです。
- 偶数配置されたインデックスにあるすべての要素に -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
クイズの作成
