根據給定值的絕對差對數組進行排序 · GeeksForGeeks 中文系列教程

# 根據給定值的絕對差對數組進行排序 > 原文： [https://www.geeksforgeeks.org/sort-an-array-according-to-absolute-difference-with-given-value/](https://www.geeksforgeeks.org/sort-an-array-according-to-absolute-difference-with-given-value/) 給定一個由 n 個不同元素組成的數組和一個數字 x，請根據與 x，i 的絕對差來排列數組元素。例如，具有最小差異的元素排在第一位，依此類推。注意：如果兩個或多個元素的距離相等，則按照與給定數組相同的順序排列它們。例子： ``` Input : arr[] : x = 7, arr[] = {10, 5, 3, 9, 2} Output : arr[] = {5, 9, 10, 3, 2} Explanation: 7 - 10 = 3(abs) 7 - 5 = 2 7 - 3 = 4 7 - 9 = 2(abs) 7 - 2 = 5 So according to the difference with X, elements are arranged as 5, 9, 10, 3, 2. Input : x = 6, arr[] = {1, 2, 3, 4, 5} Output : arr[] = {5, 4, 3, 2, 1} Input : x = 5, arr[] = {2, 6, 8, 3} Output : arr[] = {6, 3, 2, 8} ``` 想法是使用自平衡二分搜索樹。我們遍歷輸入數組，對于每個元素，我們找到它與 x 的差異，并將差異作為鍵存儲，并將元素存儲為自平衡二叉搜索樹中的值。最后，我們遍歷樹并打印其順序遍歷，這是必需的輸出。 **C++ 實現**：在 C++ 中，通過[設置](http://quiz.geeksforgeeks.org/set-associative-containers-the-c-standard-template-library-stl/)，[映射](http://quiz.geeksforgeeks.org/map-associative-containers-the-c-standard-template-library-stl/)和[多重映射](http://quiz.geeksforgeeks.org/multimap-associative-containers-the-c-standard-template-library-stl/)實現自平衡 bianry-search-tree 。我們擁有鍵值對（不僅是鍵），因此無法在此處使用 set。我們也不能直接使用 map，因為單個鍵可以屬于多個值，而 map 則允許鍵具有單個值。因此，我們使用多圖存儲鍵值對，并且鍵可以有多個值。 1. 將值以 X 為鍵將差異存儲在多圖中。 2. 在 multimap 中，值已經根據關鍵字進行排序，即與 X 的差異，因為它在內部實現了 self-balancing-binary-search-tree。 3. 用 map 的值更新 array 的所有值，以便該數組具有所需的輸出。 ## C++ ```cpp // C++ program to sort an array according absolute // difference with x. #include<bits/stdc++.h> using namespace std; // Function to sort an array according absolute // difference with x. void rearrange(int arr[], int n, int x) { ????multimap<int, int> m; ????multimap<int ,int >:: iterator it; ????// Store values in a map with the difference ????// with X as key ????for (int i = 0 ; i < n; i++) ????????m.insert(make_pair(abs(x-arr[i]),arr[i])); ????// Update the values of array ????int i = 0; ????for (it = m.begin(); it != m.end(); it++) ????????arr[i++] = (*it).second ; } // Function to print the array void printArray(int arr[] , int n) { ????for (int i = 0 ; i < n; i++) ????????cout << arr[i] << " "; } // Driver code int main() { ????int arr[] = {10, 5, 3, 9 ,2}; ????int n = sizeof(arr)/sizeof(arr[0]); ????int x = 7; ????rearrange(arr, n, x); ????printArray(arr, n); ????return 0; } ``` ## Java ```java // Java program to sort an array according absolute? // difference with x.? import java.io.*; import java.util.*; class GFG? { ????// Function to sort an array according absolute? ????// difference with x. ????static void rearrange(int[] arr, int n, int x) ????{ ????????????TreeMap<Integer, ArrayList<Integer>> m = new TreeMap<>(); ????????????// Store values in a map with the difference? ????????????// with X as key ????????????for (int i = 0; i < n; i++) ????????????{ ????????????????int diff = Math.abs(x - arr[i]); ????????????????if (m.containsKey(diff))? ????????????????{ ????????????????????ArrayList<Integer> al = m.get(diff); ????????????????????al.add(arr[i]); ????????????????????m.put(diff, al); ????????????????} ????????????????else? ????????????????{ ????????????????????????ArrayList<Integer> al = new ArrayList<>(); ????????????????????????al.add(arr[i]); ????????????????????????m.put(diff,al); ????????????????} ????????????} ????????????// Update the values of array ????????????int index = 0; ????????????for (Map.Entry entry : m.entrySet())? ????????????{ ????????????????ArrayList<Integer> al = m.get(entry.getKey()); ????????????????for (int i = 0; i < al.size(); i++) ????????????????????????arr[index++] = al.get(i);? ????????????} ????} ????// Function to print the array ????static void printArray(int[] arr, int n) ????{ ????????????for (int i = 0; i < n; i++) ????????????????System.out.print(arr[i] + " "); ????} ????// Driver code ????public static void main(String args[]) ????{ ????????????int[] arr = {10, 5, 3, 9 ,2}; ????????????int n = arr.length; ????????????int x = 7; ????????????rearrange(arr, n, x);? ????????????printArray(arr, n);? ????} } // This code is contributed by rachana soma ``` **輸出**： ``` 5 9 10 3 2 ``` **時間復雜度**：`O(N log N)` **輔助空間**：`O(n)` 本文由 [**Sahil Chhabra**](https://practice.geeksforgeeks.org/user-profile.php?user=sahil_coder) 貢獻。如果您喜歡 GeeksforGeeks 并希望做出貢獻，您還可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰寫文章，或將您的文章郵寄至 tribution@geeksforgeeks.org。查看您的文章出現在 GeeksforGeeks 主頁上，并幫助其他 Geeks。