给定一个由n个元素组成的数组，根据以下关系对数组进行排序：
null
![A[i] >= A[i-1]](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-abf3c4c26927361a6db91e80c89c8ec6_l3.png "Rendered by QuickLaTeX.com")
如果我是平的。
![A[i] <= A[i-1]](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-13cc7fc084ec83ef05b8d8f2166e1dd3_l3.png "Rendered by QuickLaTeX.com")
，如果我很奇怪的话。 打印结果数组。 例如：
Input : A[] = {1, 2, 2, 1}Output : 1 2 1 2Explanation : For 1st element, 1 1, i = 2 is even.3rd element, 1 1, i = 4 is even.Input : A[] = {1, 3, 2}Output : 1 3 2Explanation : Here, the array is also sorted as per the conditions. 1 1 and 2 < 3.
方法1- 请注意，数组由[n/2]个位置均匀的元素组成。如果我们把最大的[n/2]元素分配给偶数位置，把其余的元素分配给奇数位置，我们的问题就解决了。因为奇数位置的元素总是小于偶数位置的元素，因为它是最大元素，反之亦然。对数组进行排序，并将前[n/2]个元素分配到偶数位置。 以下是上述方法的实施情况：
C++
// C++ program to rearrange the elements // in array such that even positioned are // greater than odd positioned elements #include <bits/stdc++.h> using namespace std; void assign( int a[], int n) { // Sort the array sort(a, a + n); int ans[n]; int p = 0, q = n - 1; for ( int i = 0; i < n; i++) { // Assign even indexes with maximum elements if ((i + 1) % 2 == 0) ans[i] = a[q--]; // Assign odd indexes with remaining elements else ans[i] = a[p++]; } // Print result for ( int i = 0; i < n; i++) cout << ans[i] << " " ; } // Driver Code int main() { int A[] = { 1, 3, 2, 2, 5 }; int n = sizeof (A) / sizeof (A[0]); assign(A, n); return 0; } |
JAVA
// Java program to rearrange the elements // in array such that even positioned are // greater than odd positioned elements import java.io.*; import java.util.*; class GFG { static void assign( int a[], int n) { // Sort the array Arrays.sort(a); int ans[] = new int [n]; int p = 0 , q = n - 1 ; for ( int i = 0 ; i < n; i++) { // Assign even indexes with maximum elements if ((i + 1 ) % 2 == 0 ) ans[i] = a[q--]; // Assign odd indexes with remaining elements else ans[i] = a[p++]; } // Print result for ( int i = 0 ; i < n; i++) System.out.print(ans[i] + " " ); } // Driver code public static void main(String args[]) { int A[] = { 1 , 3 , 2 , 2 , 5 }; int n = A.length; assign(A, n); } } // This code is contributed by Nikita Tiwari. |
Python3
# Python3 code to rearrange the # elements in array such that # even positioned are greater # than odd positioned elements def assign(a, n): # Sort the array a.sort() ans = [ 0 ] * n p = 0 q = n - 1 for i in range (n): # Assign even indexes with # maximum elements if (i + 1 ) % 2 = = 0 : ans[i] = a[q] q = q - 1 # Assign odd indexes with # remaining elements else : ans[i] = a[p] p = p + 1 # Print result for i in range (n): print (ans[i], end = " " ) # Driver Code A = [ 1 , 3 , 2 , 2 , 5 ] n = len (A) assign(A, n) # This code is contributed by "Sharad_Bhardwaj". |
C#
// C# program to rearrange the elements // in array such that even positioned are // greater than odd positioned elements using System; class GFG { static void assign( int [] a, int n) { // Sort the array Array.Sort(a); int [] ans = new int [n]; int p = 0, q = n - 1; for ( int i = 0; i < n; i++) { // Assign even indexes with maximum elements if ((i + 1) % 2 == 0) ans[i] = a[q--]; // Assign odd indexes with remaining elements else ans[i] = a[p++]; } // Print result for ( int i = 0; i < n; i++) Console.Write(ans[i] + " " ); } // Driver code public static void Main() { int [] A = { 1, 3, 2, 2, 5 }; int n = A.Length; assign(A, n); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to rearrange // the elements in array such // that even positioned are // greater than odd positioned // elements function assign( $a , $n ) { // Sort the array sort( $a ); $p = 0; $q = $n - 1; for ( $i = 0; $i < $n ; $i ++) { // Assign even indexes // with maximum elements if (( $i + 1) % 2 == 0) $ans [ $i ] = $a [ $q --]; // Assign odd indexes // with remaining elements else $ans [ $i ] = $a [ $p ++]; } // Print result for ( $i = 0; $i < $n ; $i ++) echo ( $ans [ $i ] . " " ); } // Driver Code $A = array ( 1, 3, 2, 2, 5 ); $n = sizeof( $A ); assign( $A , $n ); // This code is contributed by Ajit. ?> |
Javascript
<script> // JavaScript program to rearrange the elements // in array such that even positioned are // greater than odd positioned elements function assign(a, n) { // Sort the array a.sort(); let ans = []; let p = 0, q = n - 1; for (let i = 0; i < n; i++) { // Assign even indexes with maximum elements if ((i + 1) % 2 == 0) ans[i] = a[q--]; // Assign odd indexes with remaining elements else ans[i] = a[p++]; } // Print result for (let i = 0; i < n; i++) document.write(ans[i] + " " ); } // Driver code let A = [ 1, 3, 2, 2, 5 ]; let n = A.length; assign(A, n); </script> |
输出：
1 5 2 3 2
时间复杂度：O（n*logn）
辅助空间：O（n） 方法2- 另一种方法是从第二个元素遍历数组，如果条件不满足，则将该元素与前一个元素交换。具体实施如下：
C++
// C++ program to rearrange the elements // in the array such that even positioned are // greater than odd positioned elements #include <bits/stdc++.h> using namespace std; // swap two elements void swap( int * a, int * b) { int temp = *a; *a = *b; *b = temp; } void rearrange( int arr[], int n) { for ( int i = 1; i < n; i++) { // if index is even if (i % 2 == 0) { if (arr[i] > arr[i - 1]) swap(&arr[i - 1], &arr[i]); } // if index is odd else { if (arr[i] < arr[i - 1]) swap(&arr[i - 1], &arr[i]); } } } int main() { int n = 5; int arr[] = { 1, 3, 2, 2, 5 }; rearrange(arr, n); for ( int i = 0; i < n; i++) cout << arr[i] << " " ; cout << "" ; return 0; } |
JAVA
// Java program to rearrange the elements // in the array such that even positioned are // greater than odd positioned elements class GFG { public static void rearrange( int [] arr, int n) { for ( int i = 1 ; i < n; i++) { // if index is even if (i % 2 == 0 ) { if (arr[i] > arr[i - 1 ]) { // swap two elements int temp = arr[i]; arr[i] = arr[i - 1 ]; arr[i - 1 ] = temp; } } // if index is odd else { if (arr[i] < arr[i - 1 ]) { // swap two elements int temp = arr[i]; arr[i] = arr[i - 1 ]; arr[i - 1 ] = temp; } } } for ( int i = 0 ; i < n; i++) { System.out.print(arr[i] + " " ); } } // Driver code public static void main(String []args) { int n = 5 ; int arr[] = { 1 , 3 , 2 , 2 , 5 }; rearrange(arr, n); } } // This code is contributed by avanitrachhadiya2155 |
Python3
# Python3 program to rearrange # the elements in the array # such that even positioned are # greater than odd positioned elements def rearrange(arr, n): for i in range ( 1 , n): # if index is even if (i % 2 = = 0 ): if (arr[i] > arr[i - 1 ]): arr[i - 1 ], arr[i] = arr[i], arr[i - 1 ] # if index is odd else : if (arr[i] < arr[i - 1 ]): arr[i - 1 ], arr[i] = arr[i] , arr[i - 1 ] if __name__ = = "__main__" : n = 5 arr = [ 1 , 3 , 2 , 2 , 5 ] rearrange(arr, n); for i in range (n): print (arr[i], end = " " ) print () # This code is contributed by Chitranayal |
C#
// C# program to rearrange the elements // in the array such that even positioned are // greater than odd positioned elements using System; class GFG { public static void rearrange( int [] arr, int n) { for ( int i = 1; i < n; i++) { // if index is even if (i % 2 == 0) { if (arr[i] > arr[i - 1]) { // swap two elements int temp = arr[i]; arr[i] = arr[i - 1]; arr[i - 1] = temp; } } // if index is odd else { if (arr[i] < arr[i - 1]) { // swap two elements int temp = arr[i]; arr[i] = arr[i - 1]; arr[i - 1] = temp; } } } for ( int i = 0; i < n; i++) { Console.Write(arr[i] + " " ); } } // Driver code public static void Main(String []args) { int n = 5; int []arr = {1, 3, 2, 2, 5}; rearrange(arr, n); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // JavaScript program to rearrange the elements // in the array such that even positioned are // greater than odd positioned elements function rearrange(arr, n) { for (let i = 1; i < n; i++) { // if index is even if (i % 2 == 0) { if (arr[i] > arr[i - 1]) { // swap two elements let temp = arr[i]; arr[i] = arr[i - 1]; arr[i - 1] = temp; } } // if index is odd else { if (arr[i] < arr[i - 1]) { // swap two elements let temp = arr[i]; arr[i] = arr[i - 1]; arr[i - 1] = temp; } } } for (let i = 0; i < n; i++) { document.write(arr[i] + " " ); } } // Driver code let n = 5; let arr = [1, 3, 2, 2, 5]; rearrange(arr, n); </script> |
输出：
1 3 2 5 2
时间复杂性： O（n）
辅助空间： O（1）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
