配列回文を作成するためのマージ操作の最小数を見つける


難易度 簡単に
よく聞かれる アコライト Adobe Amazon (アマゾン) フォーカイテス
配列 貪欲 数学

問題文

あなたは与えられます 配列 整数の。 問題ステートメントは、配列パリンドロームを作成するためのマージ操作の最小数を見つけること、つまり、アレイをパリンドロームにするために実行されるマージ操作の最小数を見つけることを要求します。 マージ操作とは、隣接する要素の合計を合計自体に置き換えることができることを意味します。

arr[] = {1, 4, 6, 6, 5}
1

説明:1と4をそれらの合計とマージできるため、5になり、配列は{5、6、6、5}になります。これは回文です。

arr[] = {2,1,2,4,3}
2

説明:1と2をそれらの合計とマージできるため、3になり、2と4もマージできるため、配列は{3、6、3}になります。

 

配列回文を作成するためのマージ操作の最小数を見つけるアルゴリズム

1. Set the value of output to 0.
2. Traverse the array from i = 0 and j = n – 1, to i < n( length of an array).
  1. If arr[i] is equal to arr[j]
    1. Do i++ and j--.
  2. If arr[i] > arr[j]
    1. Do j—
    2. Update and restore the value of arr[j] = arr[j] + arr[j+1].
    3. Increase the output’s value by 1.
  3. If arr[i] < arr[j],
    1. Increase the value of i.
    2. Update arr[i] = arr[i] + arr[i-1].
    3. Increase the output’s value by 1.
3. Return output.

 

説明

整数の配列を指定しました。 の最小数を見つけるように求められます マージ 配列を作成するために配列に対して実行できる操作 回文 アレイ。 ここでのマージとは、XNUMXつの隣接する値を合計し、それらの合計に置き換えることを意味します。 ここでは、実行する操作の数を確認します。

配列を左からトラバースし、右からトラバースして、XNUMXつのポインターが各トラバーサルインデックスの位置を示すようにします。 回文かどうかを確認する必要があるため、両側を選択しました。 そして、インデックスによると両側からの回文では、要素は文字列回文の場合と同じです。 そこで、反対側の値をチェックし、それらのインデックスを操作します。 次に、マージ操作を実行し、実行するマージ操作の数が見つかるまで続行します。

左からの最初の要素と右からの最初の要素が等しいかどうかを確認します。 次に、ポインタを中央のXNUMX単位に向けてシフトします。 左ポインタインデックス要素が右ポインタインデックス要素より大きいかどうかを確認してから、右ポインタ値の値を減らし、隣接する要素の合計でarr [j]を更新し、出力の値を増やすと、オペレーション。

左ポインタインデックス要素が右ポインタインデックス要素よりも小さいかどうかを確認してから、左ポインタ値の値を増やし、隣接する要素の合計でarr [i]を更新し、出力の値を増やすと、操作の数。 そして最後に、出力値を返します。

配列回文を作成するためのマージ操作の最小数を見つける

配列回文を作成するためのマージ操作の最小数を見つけるためのコード

C ++コード

#include<iostream>

using namespace std;

int getMinimumOperation(int arr[], int n)
{
    int output = 0;

    for (int i=0,j=n-1; i<=j;)
    {
        if (arr[i] == arr[j])
        {
            i++;
            j--;
        }
        else if (arr[i] > arr[j])
        {
            j--;
            arr[j] += arr[j+1] ;
            output++;
        }
        else
        {
            i++;
            arr[i] += arr[i-1];
            output++;
        }
    }
    return output;
}
int main()
{
    int arr[] = { 1, 4, 6, 6, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Minimum operations to be done: "<< getMinimumOperation(arr, n);
    return 0;
}
Minimum operations to be done: 1

 

Javaコード

class ArrayPalindromeMerging
{
    public static int getMinimumOperation(int[] arr, int n)
    {
        int output = 0;
        for (int i=0,j=n-1; i<=j;)
        {
            if (arr[i] == arr[j])
            {
                i++;
                j--;
            }
            else if (arr[i] > arr[j])
            {
                j--;
                arr[j] += arr[j+1] ;
                output++;
            }
            else
            {
                i++;
                arr[i] += arr[i-1];
                output++;
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = { 1, 4, 6, 6, 5} ;
        System.out.println("Minimum operations to be done : "+ getMinimumOperation(arr, arr.length));
    }
}
Minimum operations to be done : 1

 

複雑さの分析

時間の複雑さ

配列をXNUMX回トラバースするだけなので、これは線形時間計算量としてカウントされます。 O(N) where 「n」 配列の要素数です。

スペースの複雑さ

入力を格納するためにサイズnの単一の配列を使用しているだけなので、配列パリンドロームを作成するためのマージ操作の数を見つけるためのこのアルゴリズムは、線形空間の複雑さを持っています。 O(N) where 「n」 配列の要素数です。