给定一个正数和负数数组，对它们进行排列，使所有负整数出现在数组中所有正整数之前，而无需使用哈希表、数组等任何附加数据结构。应保持出现顺序。 例如：
null
Input : arr[] = [12, 11, -13, -5, 6, -7, 5, -3, -6]Output : arr[] = [-13, -5, -7, -3, -6, 12, 11, 6, 5]Input : arr[] = [-12, 11, 0, -5, 6, -7, 5, -3, -6]Output : arr[] = [-12, -5, -7, -3, -6, 0, 11, 6, 5]
以前的方法：已经讨论了一些方法 在这里 .它们充其量只能实施。 方法3： 还有另一种方法可以做到这一点。在C++ STL中，有一个内置函数 std:：sort（） .我们可以修改comp（）函数以获得所需的结果。因为我们必须先放置负数，然后再放置正数。我们还必须在正数和负数之间保持零（如果存在）。 此代码中的comp（）函数按所需顺序重新排列给定数组。在这里 布尔公司（内部a、内部b） ，如果整数“a”是第j个索引，而整数“b”是arr[]中的第i个索引元素，则j>i。 comp（） 函数将以这种方式调用。如果 comp（） 返回true，然后进行交换。
C++
// CPP program to rearrange positive // and negative integers keeping // order of elements. #include <bits/stdc++.h> using namespace std; bool comp( int a, int b) { // swap not needed if ((a > 0 && b > 0) || (a < 0 && b < 0) || (a > 0 && b < 0 )) return false ; // swap needed if (a < 0 && b > 0) return true ; // swap not needed if ((a == 0 && b < 0) || (a > 0 && b == 0)) return false ; // swap needed if ((a == 0 && b > 0) || (a < 0 && b == 0)) return true ; } void rearrange( int arr[], int n) { sort(arr, arr + n, comp); } // Driver code int main() { int arr[] = { -12, 11, -13, -5, 6, -7, 5, -3, -6 }; int n = sizeof (arr) / sizeof (arr[0]); rearrange(arr, n); for ( int i = 0; i < n; i++) cout << " " << arr[i]; return 0; } |
输出：
-12 -13 -5 -7 -3 -6 11 6 5
时间复杂性 与排序相同，即。 O（n日志n） .因为我们使用的是标准的排序功能。但由于内置的排序函数使用 内向型 . 方法4： 还有另一种方法可以解决这个问题。我们递归地遍历数组，将其切成两半( 数组[开始..开始] & 数组[（开始+1）…结束] ，并继续拆分数组，直到到达最后一个元素。然后我们开始合并它。其思想是，在任何时候，都要使数组保持正整数和负整数的正确顺序。合并的逻辑是： （一） 如果 数组[开始] 如果是负数，则按原样合并数组的其余部分，以保持负数的顺序。这样做的原因是，因为我们是从递归调用开始跟踪的，所以我们开始在数组中从右向左移动，从而自然地保持原始序列。 （二） 如果 数组[开始] 如果为正，则合并数组的其余部分，但在右旋转数组的一半后 数组[（开始+1）…结束] .旋转的想法是合并数组，以便 数组[开始] 总是与积极的因素融合在一起。但是，这里唯一的一点是，合并后的数组将在左侧包含所有正元素，在右侧包含所有负元素。因此，我们在每次递归中反转序列，得到负元素的原始序列，然后是正元素的原始序列。 这是可以观察到的，因为我们在每次递归中与正的第一个元素合并时反转数组，所以正的元素序列虽然在负的元素之后，但顺序是相反的。因此，作为最后一步，我们只反转最终数组的正半部分，然后得到预期的序列。 以下是上述方法的实施情况：
C++
// C++ implementation of // the above approach #include <iostream> void printArray( int array[], int length) { std::cout << "[" ; for ( int i = 0; i < length; i++) { std::cout << array[i]; if (i < (length - 1)) std::cout << ", " ; else std::cout << "]" << std::endl; } } void reverse( int array[], int start, int end) { while (start < end) { int temp = array[start]; array[start] = array[end]; array[end] = temp; start++; end--; } } // Rearrange the array with all negative integers // on left and positive integers on right // use recursion to split the array with first element // as one half and the rest array as another and then // merge it with head of the array in each step void rearrange( int array[], int start, int end) { // exit condition if (start == end) return ; // rearrange the array except the first // element in each recursive call rearrange(array, (start + 1), end); // If the first element of the array is positive, // then right-rotate the array by one place first // and then reverse the merged array. if (array[start] >= 0) { reverse(array, (start + 1), end); reverse(array, start, end); } } // Driver code int main() { int array[] = {-12, -11, -13, -5, -6, 7, 5, 3, 6}; int length = ( sizeof (array) / sizeof (array[0])); int countNegative = 0; for ( int i = 0; i < length; i++) { if (array[i] < 0) countNegative++; } std::cout << "array: " ; printArray(array, length); rearrange(array, 0, (length - 1)); reverse(array, countNegative, (length - 1)); std::cout << "rearranged array: " ; printArray(array, length); return 0; } |
JAVA
// Java program to implement the // above approach import java.io.*; class GFG{ static void printArray( int [] array, int length) { System.out.print( "[" ); for ( int i = 0 ; i < length; i++) { System.out.print(array[i]); if (i < (length - 1 )) System.out.print( "," ); else System.out.print( "]" ); } } static void reverse( int [] array, int start, int end) { while (start < end) { int temp = array[start]; array[start] = array[end]; array[end] = temp; start++; end--; } } // Rearrange the array with // all negative integers on left // and positive integers on right // use recursion to split the // array with first element // as one half and the rest // array as another and then // merge it with head of // the array in each step static void rearrange( int [] array, int start, int end) { // exit condition if (start == end) return ; // rearrange the array // except the first element // in each recursive call rearrange(array, (start + 1 ), end); // If the first element of // the array is positive, // then right-rotate the // array by one place first // and then reverse the merged array. if (array[start] >= 0 ) { reverse(array, (start + 1 ), end); reverse(array, start, end); } } // Driver code public static void main(String[] args) { int [] array = {- 12 , - 11 , - 13 , - 5 , - 6 , 7 , 5 , 3 , 6 }; int length = array.length; int countNegative = 0 ; for ( int i = 0 ; i < length; i++) { if (array[i] < 0 ) countNegative++; } System.out.print( "array: " ); printArray(array, length); rearrange(array, 0 , (length - 1 )); reverse(array, countNegative, (length - 1 )); System.out.print( "rearranged array: " ); printArray(array, length); } } // This code is contributed by Chitranayal |
Python3
# Python3 implementation of the above approach def printArray(array, length): print ( "[" , end = "") for i in range (length): print (array[i], end = "") if (i < (length - 1 )): print ( "," , end = " " ) else : print ( "]" ) def reverse(array, start, end): while (start < end): temp = array[start] array[start] = array[end] array[end] = temp start + = 1 end - = 1 # Rearrange the array with all negative integers # on left and positive integers on right # use recursion to split the array with first element # as one half and the rest array as another and then # merge it with head of the array in each step def rearrange(array, start, end): # exit condition if (start = = end): return # rearrange the array except the first # element in each recursive call rearrange(array, (start + 1 ), end) # If the first element of the array is positive, # then right-rotate the array by one place first # and then reverse the merged array. if (array[start] > = 0 ): reverse(array, (start + 1 ), end) reverse(array, start, end) # Driver code if __name__ = = '__main__' : array = [ - 12 , - 11 , - 13 , - 5 , - 6 , 7 , 5 , 3 , 6 ] length = len (array) countNegative = 0 for i in range (length): if (array[i] < 0 ): countNegative + = 1 print ( "array: " , end = "") printArray(array, length) rearrange(array, 0 , (length - 1 )) reverse(array, countNegative, (length - 1 )) print ( "rearranged array: " , end = "") printArray(array, length) # This code is contributed by mohit kumar 29 |
C#
// C# implementation of // the above approach using System; class GFG{ static void printArray( int []array, int length) { Console.Write( "[" ); for ( int i = 0; i < length; i++) { Console.Write(array[i]); if (i < (length - 1)) Console.Write( "," ); else Console.Write( "]" ); } } static void reverse( int []array, int start, int end) { while (start < end) { int temp = array[start]; array[start] = array[end]; array[end] = temp; start++; end--; } } // Rearrange the array with // all negative integers on left // and positive integers on right // use recursion to split the // array with first element // as one half and the rest // array as another and then // merge it with head of // the array in each step static void rearrange( int []array, int start, int end) { // exit condition if (start == end) return ; // rearrange the array // except the first element // in each recursive call rearrange(array, (start + 1), end); // If the first element of // the array is positive, // then right-rotate the // array by one place first // and then reverse the merged array. if (array[start] >= 0) { reverse(array, (start + 1), end); reverse(array, start, end); } } // Driver code public static void Main( string [] args) { int []array = {-12, -11, -13, -5, -6, 7, 5, 3, 6}; int length = array.Length; int countNegative = 0; for ( int i = 0; i < length; i++) { if (array[i] < 0) countNegative++; } Console.Write( "array: " ); printArray(array, length); rearrange(array, 0, (length - 1)); reverse(array, countNegative, (length - 1)); Console.Write( "rearranged array: " ); printArray(array, length); } } // This code is contributed by Rutvik_56 |
Javascript
<script> // Javascript program to implement the // above approach function printArray(array, Length) { document.write( "[" ); for (let i = 0; i < Length; i++) { document.write(array[i]); if (i < (Length - 1)) document.write( "," ); else document.write( "]<br>" ); } } function reverse(array,start,end) { while (start < end) { let temp = array[start]; array[start] = array[end]; array[end] = temp; start++; end--; } } // Rearrange the array with // all negative integers on left // and positive integers on right // use recursion to split the // array with first element // as one half and the rest // array as another and then // merge it with head of // the array in each step function rearrange(array,start,end) { // exit condition if (start == end) return ; // rearrange the array // except the first element // in each recursive call rearrange(array, (start + 1), end); // If the first element of // the array is positive, // then right-rotate the // array by one place first // and then reverse the merged array. if (array[start] >= 0) { reverse(array, (start + 1), end); reverse(array, start, end); } } // Driver code let array = [-12, -11, -13, -5, -6, 7, 5, 3, 6]; let length = array.length; let countNegative = 0; for (let i = 0; i < length; i++) { if (array[i] < 0) countNegative++; } document.write( "array: " ); printArray(array, length); rearrange(array, 0, (length - 1)); reverse(array, countNegative, (length - 1)); document.write( "rearranged array: " ); printArray(array, length); // This code is contributed by rag2127. </script> |
输出：
array: [-12, -11, -13, -5, -6, 7, 5, 3, 6]rearranged array: [-12, -11, -13, -5, -6, 7, 5, 3, 6]
时间复杂性： O（N^2） 本文由 阿比吉特·考拉夫 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
