# 查找使數組回文的最小合并操作數 > 原文： [https://www.geeksforgeeks.org/find-minimum-number-of-merge-operations-to-make-an-array-palindrome/](https://www.geeksforgeeks.org/find-minimum-number-of-merge-operations-to-make-an-array-palindrome/) 給定一個正整數數組。 我們需要將給定的數組設為“回文”。 僅允許對數組進行的操作是合并。 合并兩個相鄰元素意味著用它們的總和替換它們。 任務是找到使給定數組成為“回文”所需的最小合并操作數。 為了使數組成為回文，我們可以簡單地將合并操作應用 n-1 次，其中 n 是數組的大小（請注意，單個元素數組總是回文，類似于單個字符串）。 在這種情況下，數組的大小將減小為 1。但是在這個問題上，我們被要求以最少的操作數來完成。 **示例**： ``` Input : arr[] = {15, 4, 15} Output : 0 Array is already a palindrome. So we do not need any merge operation. Input : arr[] = {1, 4, 5, 1} Output : 1 We can make given array palindrome with minimum one merging (merging 4 and 5 to make 9) Input : arr[] = {11, 14, 15, 99} Output : 3 We need to merge all elements to make a palindrome. ``` 預期時間復雜度為`O(n)`。 [](https://practice.geeksforgeeks.org/problem-page.php?pid=670) ## 強烈建議您在繼續解決方案之前，單擊此處進行練習。 令 f（i，j）為使子數組 arr [i..j]成為回文式的最小合并操作。 如果 i == j，答案為 0。我們從 0 開始，而 i 從 n-1 開始。 1. 如果 arr [i] == arr [j]，則無需對索引 i 或索引 j 進行任何合并操作。 在這種情況下，我們的答案將是 f（i + 1，j-1）。 2. 否則，我們需要進行合并操作。 出現以下情況。 * 如果 arr [i] > arr [j]，那么我們應該在索引 j 處進行合并操作。 我們合并索引 j-1 和 j，并更新 arr [j-1] = arr [j-1] + arr [j]。 在這種情況下，我們的答案將是 1 + f（i，j-1）。 * 對于 arr [i] < arr [j]的情況，更新 arr [i + 1] = arr [i + 1] + arr [i]。 在這種情況下，我們的答案將是 1 + f（i + 1，j）。 * 我們的答案將是 f（0，n-1），其中 n 是數組 arr []的大小。 因此，可以使用兩個指針（第一個指針指向數組的開始，第二個指針指向數組的最后一個元素）方法迭代地解決此問題，并保持到目前為止完成的合并操作總數。 以下是上述想法的實現。 ## C ``` // C++ program to find number of operations // to make an array palindrome #include <bits/stdc++.h> using namespace std; // Returns minimum number of count operations // required to make arr[] palindrome int findMinOps(int arr[], int n) { ????int ans = 0; // Initialize result ????// Start from two corners ????for (int i=0,j=n-1; i<=j;) ????{ ????????// If corner elements are same, ????????// problem reduces arr[i+1..j-1] ????????if (arr[i] == arr[j]) ????????{ ????????????i++; ????????????j--; ????????} ????????// If left element is greater, then ????????// we merge right two elements ????????else if (arr[i] > arr[j]) ????????{ ????????????// need to merge from tail. ????????????j--; ????????????arr[j] += arr[j+1] ; ????????????ans++; ????????} ????????// Else we merge left two elements ????????else ????????{ ????????????i++; ????????????arr[i] += arr[i-1]; ????????????ans++; ????????} ????} ????return ans; } // Driver program to test above int main() { ????int arr[] = {1, 4, 5, 9, 1}; ????int n = sizeof(arr)/sizeof(arr[0]); ????cout << "Count of minimum operations is " ?????????<<? findMinOps(arr, n) << endl; ????return 0; } ``` ## Java ```java // Java program to find number of operations // to make an array palindrome class GFG { ????// Returns minimum number of count operations ????// required to make arr[] palindrome ????static int findMinOps(int[] arr, int n) ????{ ????????int ans = 0; // Initialize result ????????// Start from two corners ????????for (int i=0,j=n-1; i<=j;) ????????{ ????????????// If corner elements are same, ????????????// problem reduces arr[i+1..j-1] ????????????if (arr[i] == arr[j]) ????????????{ ????????????????i++; ????????????????j--; ????????????} ????????????// If left element is greater, then ????????????// we merge right two elements ????????????else if (arr[i] > arr[j]) ????????????{ ????????????????// need to merge from tail. ????????????????j--; ????????????????arr[j] += arr[j+1] ; ????????????????ans++; ????????????} ????????????// Else we merge left two elements ????????????else ????????????{ ????????????????i++; ????????????????arr[i] += arr[i-1]; ????????????????ans++; ????????????} ????????} ????????return ans; ????} ????// Driver method to test the above function ????public static void main(String[] args) ????{ ????????int arr[] = new int[]{1, 4, 5, 9, 1} ; ????????System.out.println("Count of minimum operations is "+ ????????????????????????????????findMinOps(arr, arr.length)); ????} } ``` ## Python ``` # Python program to find number of operations # to make an array palindrome # Returns minimum number of count operations # required to make arr[] palindrome def findMinOps(arr, n): ????ans = 0 # Initialize result ????# Start from two corners ????i,j = 0,n-1 ????while i<=j: ????????# If corner elements are same, ????????# problem reduces arr[i+1..j-1] ????????if arr[i] == arr[j]: ????????????i += 1 ????????????j -= 1 ????????# If left element is greater, then ????????# we merge right two elements ????????elif arr[i] > arr[j]: ????????????# need to merge from tail. ????????????j -= 1 ????????????arr[j] += arr[j+1]? ????????????ans += 1 ????????# Else we merge left two elements ????????else: ????????????i += 1 ????????????arr[i] += arr[i-1] ????????????ans += 1 ????return ans # Driver program to test above arr = [1, 4, 5, 9, 1] n = len(arr) print("Count of minimum operations is " + str(findMinOps(arr, n))) # This code is contributed by Pratik Chhajer ``` ## C# ```cs // C# program to find number of operations // to make an array palindrome using System; class GFG { ????// Returns minimum number of count operations ????// required to make arr[] palindrome ????static int findMinOps(int []arr, int n) ????{ ????????int ans = 0; // Initialize result ????????// Start from two corners ????????for (int i = 0, j = n - 1; i <= j;) ????????{ ????????????// If corner elements are same, ????????????// problem reduces arr[i+1..j-1] ????????????if (arr[i] == arr[j]) ????????????{ ????????????????i++; ????????????????j--; ????????????} ????????????// If left element is greater, then ????????????// we merge right two elements ????????????else if (arr[i] > arr[j]) ????????????{ ????????????????// need to merge from tail. ????????????????j--; ????????????????arr[j] += arr[j + 1] ; ????????????????ans++; ????????????} ????????????// Else we merge left two elements ????????????else ????????????{ ????????????????i++; ????????????????arr[i] += arr[i-1]; ????????????????ans++; ????????????} ????????} ????????return ans; ????} ????// Driver Code ????public static void Main() ????{ ????????int []arr = new int[]{1, 4, 5, 9, 1} ; ????????Console.Write("Count of minimum operations is " + ????????????????????????????findMinOps(arr, arr.Length)); ????} } // This code is contributed by nitin mittal ``` ## PHP ```php <?php // PHP program to find number? // of operations to make an? // array palindrome // Returns minimum number of? // count operations required // to make arr[] palindrome function findMinOps($arr, $n) { ????// Initialize result ????$ans = 1;? ????// Start from two corners ????for ($i = 0, $j = $n - 1; $i <= $j?? ????{ ????????// If corner elements are same, ????????// problem reduces arr[i+1..j-1] ????????if ($arr[$i] == $arr[$j]) ????????{ ????????????$i++; ????????????$j--; ????????} ????????// If left element is greater, then ????????// we merge right two elements ????????else if ($arr[$i] > $arr[$j]) ????????{ ????????????// need to merge from tail. ????????????$j--; ????????????$arr[$j] += $arr[$j + 1] ; ????????????$ans++; ????????} ????????// Else we merge? ????????// left two elements ????????else ????????{ ????????????$i++; ????????????$arr[$i] += $arr[$i - 1]; ????????????$ans++; ????????} ????} ????return $ans; } // Driver Code $arr[] = array(1, 4, 5, 9, 1); $n = sizeof($arr); echo "Count of minimum operations is ",? ?????????????????findMinOps($arr, $n) ; // This code is contributed by nitin mittal. ?> ``` **輸出**： ``` Count of minimum operations is 1 ``` 給定程序的時間復雜度為：`O(n)`