我们有一个按升序排序的整数数组。我们还有3个整数A、B和C。我们需要对数组中的每个元素x应用A*x*x+B*x+C，并对修改后的数组进行排序。
null
例子：
Input : arr[] = {-1, 0, 1, 2, 3, 4} A = -1, B = 2, C = -1Output : {-9, -4, -4, -1, -1, 0}Input array is {-1, 0, 1, 2, 3, 4}. Afterapplying the equation A*x*x + B*x + C onevery element x we get, {-4,-1, 0, -1, -4, -9}After sorting, we get {-9, -4, -4, -1, -1, 0}
方法1（简单）： 1-将给定方程式应用于所有元素。O（n） 2-对修改后的数组进行排序。O（n日志n） O（n logn）的时间复杂度
方法2（有效）：抛物线性质 给出的方程是抛物线方程。因此，将其应用于已排序数组的结果将产生一个数组，该数组将具有最大值/最小值，子数组将在其左侧和右侧排序。 在上面的示例中，最大值为0，其左侧的子数组{-4，-1}按升序排序，其右侧的子数组{-1，-4，-9}按降序排序。 我们需要做的就是合并这些排序的数组，它们在时间上是线性的。
所以算法是：
- 对每个元素应用公式。
- 找到最大值/最小值。
- 合并子数组。
注意：下面的代码假设修改后的数组先增大后减小。
C++
// C program to sort an array after applying equation // A*x*x + B*x + C #include<bits/stdc++.h> using namespace std; // Function to sort an array after applying given // equation. void sortArray( int arr[], int n, int A, int B, int C) { // Apply equation on all elements for ( int i = 0; i < n; i++) arr[i] = A*arr[i]*arr[i] + B*arr[i] + C; // Find maximum element in resultant array int index, maximum = INT_MIN; for ( int i = 0; i< n; i++) { if (maximum < arr[i]) { index = i; maximum = arr[i]; } } // Use maximum element as a break point // and merge both subarrays using simple // merge function of merge sort int i = 0, j = n-1; int new_arr[n], k = 0; while (i < index && j > index) { if (arr[i] < arr[j]) new_arr[k++] = arr[i++]; else new_arr[k++] = arr[j--]; } // Merge remaining elements while (i < index) new_arr[k++] = arr[i++]; while (j > index) new_arr[k++] = arr[j--]; new_arr[n-1] = maximum; // Modify original array for ( int i = 0; i < n ; i++) arr[i] = new_arr[i]; } // Driver code int main() { int arr[] = {-21 ,-15, 12, 13, 14 }; int n = sizeof (arr) / sizeof (arr[0]); int A = -6, B =-7, C = 2; sortArray(arr, n, A, B, C); cout << "Array after sorting is : n" ; for ( int i=0; i<n; i++) cout << arr[i] << " " ; return 0; } |
JAVA
// Java program to sort an array after applying equation // A*x*x + B*x + C class Main { // Function to sort an array after applying given // equation. static void sortArray( int arr[], int n, int A, int B, int C) { // Apply equation on all elements for ( int i = 0 ; i < n; i++) arr[i] = A*arr[i]*arr[i] + B*arr[i] + C; // Find maximum element in resultant array int index=- 1 ; int maximum = - 999999 ; for ( int i = 0 ; i< n; i++) { if (maximum < arr[i]) { index = i; maximum = arr[i]; } } // Use maximum element as a break point // and merge both subarrays using simple // merge function of merge sort int i = 0 , j = n- 1 ; int [] new_arr = new int [n]; int k = 0 ; while (i < index && j > index) { if (arr[i] < arr[j]) new_arr[k++] = arr[i++]; else new_arr[k++] = arr[j--]; } // Merge remaining elements while (i < index) new_arr[k++] = arr[i++]; while (j > index) new_arr[k++] = arr[j--]; new_arr[n- 1 ] = maximum; // Modify original array for ( int p = 0 ; p < n ; p++) arr[p] = new_arr[p]; } // main function public static void main (String[] args) { int arr[] = {- 21 ,- 15 , 12 , 13 , 14 }; int n = arr.length; int A = - 6 , B =- 7 , C = 2 ; sortArray(arr, n, A, B, C); System.out.println( "Array after sorting is : " ); for ( int i= 0 ; i<n; i++) System.out.print(arr[i]+ " " ); } } /* This code is contributed by Harsh Agarwal */ |
Python3
# Python3 program to sort an # array after applying equation # A*x*x + B*x + C import sys # Function to sort an array # after applying given equation. def sortArray(arr, n, A, B, C): # Apply equation on all elements for i in range (n): arr[i] = (A * arr[i] * arr[i] + B * arr[i] + C) index = - (sys.maxsize - 1 ) maximum = - (sys.maxsize - 1 ) # Find maximum element in # resultant array for i in range (n): if maximum < arr[i]: index = i maximum = arr[i] # Use maximum element as a break point # and merge both subarrays using simple # merge function of merge sort i = 0 ; j = n - 1 ; new_arr = [ 0 ] * n k = 0 while i < index and j > index: if arr[i] < arr[j]: new_arr[k] = arr[i] k + = 1 i + = 1 else : new_arr[k] = arr[j] k + = 1 j - = 1 # Merge remaining elements while i < index: new_arr[k] = arr[i] k + = 1 i + = 1 # Modify original array while j > index: new_arr[k] = arr[j] k + = 1 j - = 1 new_arr[n - 1 ] = maximum for i in range (n): arr[i] = new_arr[i] # Driver code arr = [ - 21 , - 15 , 12 , 13 , 14 ] n = len (arr) A = - 6 B = - 7 C = 2 sortArray(arr, n, A, B, C) print ( "Array after sorting is:" ) for i in range (n): print (arr[i], end = " " ) # This code is contributed # by Shrikant13 |
C#
// C# program to sort an array after applying equation // A*x*x + B*x + C using System; class MAIN { // Function to sort an array after applying given // equation. static void sortArray( int [] arr, int n, int A, int B, int C) { // Apply equation on all elements for ( int i = 0; i < n; i++) arr[i] = A*arr[i]*arr[i] + B*arr[i] + C; // Find maximum element in resultant array int index=-1; int maximum = -999999; for ( int i = 0; i< n; i++) { if (maximum < arr[i]) { index = i; maximum = arr[i]; } } // Use maximum element as a break point // and merge both subarrays using simple // merge function of merge sort int l = 0, j = n-1; int [] new_arr = new int [n]; int k = 0; while (l < index && j > index) { if (arr[l] < arr[j]) new_arr[k++] = arr[l++]; else new_arr[k++] = arr[j--]; } // Merge remaining elements while (l < index) new_arr[k++] = arr[l++]; while (j > index) new_arr[k++] = arr[j--]; new_arr[n-1] = maximum; // Modify original array for ( int p = 0; p < n ; p++) arr[p] = new_arr[p]; } // main function public static void Main () { int [] arr = {-21 ,-15, 12, 13, 14 }; int n = arr.Length; int A = -6, B =-7, C = 2; sortArray(arr, n, A, B, C); Console.Write( "Array after sorting is : " + "" ); for ( int i=0; i<n; i++) Console.Write(arr[i]+ " " ); } } |
PHP
<?php // PHP program to sort an array after // applying equation A*x*x + B*x + C // Function to sort an array after // applying given equation. function sortArray(& $arr , $n , $A , $B , $C ) { // Apply equation on all elements for ( $i = 0; $i < $n ; $i ++) $arr [ $i ] = $A * $arr [ $i ] * $arr [ $i ] + $B * $arr [ $i ] + $C ; // Find maximum element in // resultant array $index = 0; $maximum = PHP_INT_MIN; for ( $i = 0; $i < $n ; $i ++) { if ( $maximum < $arr [ $i ]) { $index = $i ; $maximum = $arr [ $i ]; } } // Use maximum element as a break point // and merge both subarrays using simple // merge function of merge sort $i = 0; $j = $n - 1; $new_arr = array (); while ( $i < $index && $j > $index ) { if ( $arr [ $i ] < $arr [ $j ]) array_push ( $new_arr , $arr [ $i ++]); else array_push ( $new_arr , $arr [ $j --]); } // Merge remaining elements while ( $i < $index ) array_push ( $new_arr , $arr [ $i ++]); while ( $j > $index ) array_push ( $new_arr , $arr [ $j --]); array_push ( $new_arr , $maximum ); // Modify original array for ( $i = 0; $i < count ( $new_arr ) ; $i ++) $arr [ $i ] = $new_arr [ $i ]; } // Driver code $arr = array (-21 ,-15, 12, 13, 14 ); $n = count ( $arr ); $A = -6; $B = -7; $C = 2; sortArray( $arr , $n , $A , $B , $C ); echo "Array after sorting is : " ; for ( $i = 0; $i < $n ; $i ++) echo $arr [ $i ] . " " ; // This code is contributed by mits ?> |
Javascript
<script> function sortArray(arr,n,A,B,C) { // Apply equation on all elements for (let i = 0; i < n; i++) arr[i] = A*arr[i]*arr[i] + B*arr[i] + C; // Find maximum element in resultant array let index=-1; let maximum = -999999; for (let i = 0; i< n; i++) { if (maximum < arr[i]) { index = i; maximum = arr[i]; } } // Use maximum element as a break point // and merge both subarrays using simple // merge function of merge sort let i = 0, j = n-1; let new_arr = new Array(n); for (let i=0;i<n;i++) { new_arr[i]=0; } let k = 0; while (i < index && j > index) { if (arr[i] < arr[j]) new_arr[k++] = arr[i++]; else new_arr[k++] = arr[j--]; } // Merge remaining elements while (i < index) new_arr[k++] = arr[i++]; while (j > index) new_arr[k++] = arr[j--]; new_arr[n-1] = maximum; // Modify original array for (let p = 0; p < n ; p++) arr[p] = new_arr[p]; } let arr=[-21 ,-15, 12, 13, 14]; let n = arr.length; let A = -6, B =-7, C = 2; sortArray(arr, n, A, B, C); document.write( "Array after sorting is : <br>" ); for (let i=0; i<n; i++) document.write(arr[i]+ " " ); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
Array after sorting is : -2497 -1272 -1243 -1103 -946
时间复杂性： O（n） 辅助空间： O（n）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
