배열 회문을 만들기위한 최소 병합 작업 수 찾기

난이도 쉽게
자주 묻는 질문 수행자 어도비 벽돌 아마존 포카이트
배열 탐욕스러운 수학조회수 23

문제 정책

당신은 주어진 정렬 정수 문제 설명은 배열 회문을 만들기 위해 병합 작업의 최소 수를 찾습니다. 즉, 회문으로 만들기 위해 배열에서 수행 할 병합 작업의 최소 수를 찾습니다. 병합 연산은 단순히 인접한 요소의 합계를 합계로 바꿀 수 있음을 의미합니다.

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.

 

설명

정수 배열을 제공했습니다. 우리는 최소한의 수를 찾아야합니다. 합병 배열에 수행 할 수있는 작업을 회문 정렬. 여기서 병합은 두 개의 인접한 값을 더하고 합산하는 것을 의미합니다. 여기서 우리는 수행 할 작업의 수를 찾을 것입니다.

왼쪽과 오른쪽에서 배열을 순회하여 두 개의 포인터가 각 순회 인덱스의 위치를 ​​나타내도록 할 것입니다. 회문인지 아닌지를 확인해야하기 때문에 양쪽을 선택했습니다. 그리고 인덱스에 따라 양쪽에서 회문에서 요소는 문자열 회문에서와 같이 동일합니다. 그래서 우리는 반대편의 가치를 확인하고 그들의 인덱스를 조작 할 것입니다. 그런 다음 병합 작업을 수행하고 수행 할 병합 작업 수를 찾을 때까지 계속합니다.

왼쪽과 오른쪽에서 첫 번째 요소가 같은지 확인합니다. 그런 다음 포인터를 중앙으로 한 단위 이동하십시오. 왼쪽 포인터 인덱스 요소가 오른쪽 포인터 인덱스 요소보다 큰지 확인한 다음 오른쪽 포인터 값의 값을 줄이고 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

 

자바 코드

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

 

복잡성 분석

시간 복잡성

우리는 단순히 어레이를 한 번 순회하고 있으므로 이것은 선형 시간 복잡성을 고려합니다. O (N) 어디에 "엔" 배열의 요소 수입니다.

공간 복잡성

입력을 저장하기 위해 크기가 n 인 단일 배열을 사용하고 있으므로 배열 회문을 만들기 위해 병합 작업 수를 찾는이 알고리즘은 선형 공간 복잡성을 갖습니다. O (N) 어디에 "엔" 배열의 요소 수입니다.

Translate »