Проверьте, можно ли сделать два массива равными, перевернув любой подмассив один раз

Опубликовано: 9 Января, 2022

Для двух массивов A [] и B [] равного размера N задача состоит в том, чтобы проверить, можно ли сделать A [] равным B [] путем обращения любого подмассива A только один раз.

Примеры:

Input: A[] = {1, 3, 2, 4}
B[] = {1, 2, 3, 4}
Output: Yes
Explanation:
The sub-array {3, 2} can be reversed to {2, 3}, which makes A equal to B.

Input: A[] = {1, 4, 2, 3}
B[] = {1, 2, 3, 4}
Output: No
Explanation:
There is no sub-array of A which, when reversed, makes A equal to B.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход: проверьте все подмассивы A [] и сравните два массива после реверсирования подмассивов.
Временная сложность: O (N ² ).

Эффективный подход:

Сначала найдите начальный и конечный индексы подмассива, не равные в A и B.
Затем, перевернув требуемый подмассив, мы можем проверить, можно ли сделать A равным B или нет.
Начальный индекс - это первый индекс в массивах, для которых A [i]! = B [i], а конечный индекс - это последний индекс в массивах, для которых A [i]! = B [i] .

Below is the implementation of the above approach.

C++

// C++ implementation to
// check whether two arrays
// can be made equal by
// reversing a sub-array
// only once
#include <bits/stdc++.h>
using namespace std;
 
// Function to check whether two arrays
// can be made equal by reversing
// a sub-array only once
void checkArray(int A[], int B[], int N)
{
    // Integer variable for
    // storing the required
    // starting and ending
    // indices in the array
    int start = 0;
    int end = N - 1;
 
    // Finding the smallest index
    // for which A[i] != B[i]
    // i.e the starting index
    // of the unequal sub-array
    for (int i = 0; i < N; i++) {
        if (A[i] != B[i]) {
            start = i;
            break;
        }
    }
    // Finding the largest index
    // for which A[i] != B[i]
    // i.e the ending index
    // of the unequal sub-array
    for (int i = N - 1; i >= 0; i--) {
        if (A[i] != B[i]) {
            end = i;
            break;
        }
    }
 
    // Reversing the sub-array
    // A[start], A[start+1] .. A[end]
    reverse(A + start, A + end + 1);
 
    // Checking whether on reversing
    // the sub-array A[start]...A[end]
    // makes the arrays equal
 
    for (int i = 0; i < N; i++) {
        if (A[i] != B[i]) {
            // If any element of the
            // two arrays is unequal
            // print No and return
            cout << "No" << endl;
            return;
        }
    }
    // Print Yes if arrays are
    // equal after reversing
    // the sub-array
    cout << "Yes" << endl;
}
// Driver code
int main()
{
    int A[] = { 1, 3, 2, 4 };
    int B[] = { 1, 2, 3, 4 };
    int N = sizeof(A) / sizeof(A[0]);
    checkArray(A, B, N);
 
    return 0;
}

Java

// Java implementation to
// check whether two arrays
// can be made equal by
// reversing a sub-array
// only once
import java.util.*;
class GFG{
  
// Function to check whether two arrays
// can be made equal by reversing
// a sub-array only once
static void checkArray(int A[], int B[], int N)
{
    // Integer variable for
    // storing the required
    // starting and ending
    // indices in the array
    int start = 0;
    int end = N - 1;
  
    // Finding the smallest index
    // for which A[i] != B[i]
    // i.e the starting index
    // of the unequal sub-array
    for (int i = 0; i < N; i++)
    {
        if (A[i] != B[i])
        {
            start = i;
            break;
        }
    }
    // Finding the largest index
    // for which A[i] != B[i]
    // i.e the ending index
    // of the unequal sub-array
    for (int i = N - 1; i >= 0; i--)
    {
        if (A[i] != B[i])
        {
            end = i;
            break;
        }
    }
  
    // Reversing the sub-array
    // A[start], A[start+1] .. A[end]
    Collections.reverse(Arrays.asList(A));
  
    // Checking whether on reversing
    // the sub-array A[start]...A[end]
    // makes the arrays equal
    for (int i = 0; i < N; i++)
    {
        if (A[i] != B[i])
        {
            // If any element of the
            // two arrays is unequal
            // print No and return
            System.out.println("Yes");
            return;
        }
    }
    // Print Yes if arrays are
    // equal after reversing
    // the sub-array
   System.out.println("Yes");
}
// Driver code
public static void main(String[] args)
{
    int A[] = { 1, 3, 2, 4 };
    int B[] = { 1, 2, 3, 4 };
    int N = A.length;
    checkArray(A, B, N);
}
}
 
// This Code is contributed by rock_cool

Python3

# Python3 implementation to
# check whether two arrays
# can be made equal by
# reversing a sub-array
# only once
 
# Function to check whether two arrays
# can be made equal by reversing
# a sub-array only once
def checkArray(A, B, N):
     
    # Integer variable for
    # storing the required
    # starting and ending
    # indices in the array
    start = 0
    end = N - 1
 
    # Finding the smallest index
    # for which A[i] != B[i]
    # i.e the starting index
    # of the unequal sub-array
    for i in range(N):
        if (A[i] != B[i]):
            start = i
            break
             
    # Finding the largest index
    # for which A[i] != B[i]
    # i.e the ending index
    # of the unequal sub-array
    for i in range(N - 1, -1, -1):
        if (A[i] != B[i]):
            end = i
            break
 
    # Reversing the sub-array
    # A[start], A[start+1] .. A[end]
    A[start:end + 1] = reversed(A[start:end + 1])
     
    # Checking whether on reversing
    # the sub-array A[start]...A[end]
    # makes the arrays equal
    for i in range(N):
        if (A[i] != B[i]):
             
            # If any element of the
            # two arrays is unequal
            # print No and return
            print("No")
            return
             
    # Print Yes if arrays are
    # equal after reversing
    # the sub-array
    print("Yes")
     
# Driver code
if __name__ == "__main__":
     
    A = [ 1, 3, 2, 4 ]
    B = [ 1, 2, 3, 4 ]
    N = len(A)
     
    checkArray(A, B, N)
     
# This code is contributed by mohit kumar 29

C#

// C# implementation to
// check whether two arrays
// can be made equal by
// reversing a sub-array
// only once
using System;
 
class GFG{
 
// Function to check whether two arrays
// can be made equal by reversing
// a sub-array only once
static void checkArray(int []A, int []B, int N)
{
     
    // Integer variable for
    // storing the required
    // starting and ending
    // indices in the array
    int start = 0;
    int end = N - 1;
 
    // Finding the smallest index
    // for which A[i] != B[i]
    // i.e the starting index
    // of the unequal sub-array
    for(int i = 0; i < N; i++)
    {
        if (A[i] != B[i])
        {
            start = i;
            break;
        }
    }
     
    // Finding the largest index
    // for which A[i] != B[i]
    // i.e the ending index
    // of the unequal sub-array
    for(int i = N - 1; i >= 0; i--)
    {
        if (A[i] != B[i])
        {
            end = i;
            break;
        }
    }
 
    // Reversing the sub-array
    // A[start], A[start+1] .. A[end]
    Array.Reverse(A, start, end);
 
 
    // Checking whether on reversing
    // the sub-array A[start]...A[end]
    // makes the arrays equal
    for(int i = 0; i < N; i++)
    {
        if (A[i] != B[i])
        {
             
            // If any element of the
            // two arrays is unequal
            // print No and return
            Console.Write("Yes");
            return;
        }
    }
     
    // Print Yes if arrays are
    // equal after reversing
    // the sub-array
    Console.Write("Yes");
}
 
// Driver code
public static void Main(string[] args)
{
    int []A = { 1, 3, 2, 4 };
    int []B = { 1, 2, 3, 4 };
    int N = A.Length;
    checkArray(A, B, N);
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
 
 
// Javascript implementation to
// check whether two arrays
// can be made equal by
// reversing a sub-array
// only once
 
// Function to check whether two arrays
// can be made equal by reversing
// a sub-array only once
function checkArray(A, B, N)
{
    // Integer variable for
    // storing the required
    // starting and ending
    // indices in the array
    var start = 0;
    var end = N - 1;
 
    // Finding the smallest index
    // for which A[i] != B[i]
    // i.e the starting index
    // of the unequal sub-array
    for (var i = 0; i < N; i++) {
        if (A[i] != B[i]) {
            start = i;
            break;
        }
    }
    // Finding the largest index
    // for which A[i] != B[i]
    // i.e the ending index
    // of the unequal sub-array
    for (var i = N - 1; i >= 0; i--) {
        if (A[i] != B[i]) {
            end = i;
            break;
        }
    }
 
    // Reversing the sub-array
    // A[start], A[start+1] .. A[end]
    var l = start;
    var r = end;
    var d = parseInt((r-l+2)/2);
      for(var i=0;i<d;i++)
      {
         var t = A[l+i];
         A[l+i] = A[r-i];
         A[r-i] = t;
      }
 
    // Checking whether on reversing
    // the sub-array A[start]...A[end]
    // makes the arrays equal
 
    for (var i = 0; i < N; i++) {
        if (A[i] != B[i]) {
            // If any element of the
            // two arrays is unequal
            // print No and return
            document.write( "No" );
            return;
        }
    }
    // Print Yes if arrays are
    // equal after reversing
    // the sub-array
    document.write( "Yes" );
}
// Driver code
var A = [1, 3, 2, 4];
var B = [1, 2, 3, 4];
var N = A.length;
checkArray(A, B, N);
 
 
</script>

Output:

Yes

Сложность времени: O (N)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Структуры данных

Проверьте, можно ли сделать два массива равными, перевернув любой подмассив один раз

C++

Java

Python3

C#

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ