应用给定方程后对数组排序 · GeeksForGeeks 中文系列教程

# 应用给定方程后对数组排序 > 原文： [https://www.geeksforgeeks.org/sort-array-applying-given-equation/](https://www.geeksforgeeks.org/sort-array-applying-given-equation/) 我们有一个按升序排序的整数数组。我们也有 3 个整数 A，B 和 C。我们需要对数组中的每个元素 x 应用 A * x * x + B * x + C，并对修改后的数组进行排序。 **例如**： ``` Input : arr[] = {-1, 0, 1, 2, 3, 4} A = -1, B = 2, C = -1 Output : {-9, -4, -4, -1, -1, 0} Input array is {-1, 0, 1, 2, 3, 4}. After applying the equation A*x*x + B*x + C on every element x we get, {-4,-1, 0, -1, -4, -9} After sorting, we get {-9, -4, -4, -1, -1, 0} ``` 询问：Adobe **方法 1（简单）**： 1-将给定的方程式应用于所有元素。`O(n)` 2-对修改后的数组进行排序。 O（n 对数 n） `O(N log N)`的时间复杂度 **方法 2（有效）：抛物线属性** 给出的方程是抛物线的。因此，将其应用于已排序数组的结果将导致一个数组，该数组的最大值和最小值与其子数组的左侧和右侧进行排序。在上面的示例中，maximum 为 0，其左侧{-4，-1}的子数组以升序排序，其右侧{-1，-4，-9}的子数组以降序排序。所有我们需要做的是合并这些排序的数组，这些数组在时间上是线性的。所以算法是： 1. 在每个元素上应用方程式。 2. 查找最大值/最小值。 3. 合并子数组。注意：以下代码假定修改后的数组先增大然后减小。 ## C++ ```cpp // 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 usin 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 // 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 usin 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 ```py # 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 usin 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# ```cs // 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 usin 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 : "+"\n"); for (int i=0; i<n; i++) Console.Write(arr[i]+" "); } } ``` ## PHP ```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 usin 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 : \n"; for ($i = 0; $i < $n; $i++) echo $arr[$i] . " "; // This code is contributed by mits ?> ``` **输出**： ``` Array after sorting is : -2497 -1272 -1243 -1103 -946 ``` **时间复杂度**：`O(n)` **辅助空间**：`O(n)` **参考**： [http://stackoverflow.com/questions/4551599/sorting-result-array](http://stackoverflow.com/questions/4551599/sorting-result-array) 本文由 [**Sahil Chhabra**](https://www.facebook.com/sahil.chhabra.965) 贡献。如果您喜欢 GeeksforGeeks 并希望做出贡献，则还可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰写文章，或将您的文章邮寄至 tribution@geeksforgeeks.org。查看您的文章出现在 GeeksforGeeks 主页上，并帮助其他 Geeks。