Рубрики

Проверьте, является ли Массив Subarray другого Массива

Даны два массива A [] и B [], состоящие из и целые числа. Задача состоит в том, чтобы проверить, является ли массив B [] подмассивом массива A [] или нет.

Примеры :

Input : A[] = {2, 3, 0, 5, 1, 1, 2}, B[] = {3, 0, 5, 1}
Output : Yes

Input : A[] = {1, 2, 3, 4, 5}, B[] = {2, 5, 6}
Output : No

Источник : Visa Interview Experience

Простой подход . Простой подход состоит в том, чтобы запустить два вложенных цикла и сгенерировать все подмассивы массива A [] и использовать еще один цикл, чтобы проверить, равен ли какой-либо из подмассивов A [] массиву B [].

Эффективный подход . Эффективный подход заключается в использовании двух указателей для одновременного обхода массива. Сохраняйте указатель массива B [] неподвижно, и если какой-либо элемент из A [] совпадает с первым элементом B [], то увеличьте указатель обоих массивов, иначе увеличьте указатель A и сбросьте указатель B до 0. Если все элементы B совпадают, затем выведите YES, иначе выведите NO.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ программа для проверки, является ли массив
// подмассив другого массива

  
#include <bits/stdc++.h>

using namespace std;

  
// Функция для проверки, является ли массив
// подмассив другого массива

bool isSubArray(int A[], int B[], int n, int m)

{

    // Два указателя для обхода массивов

    int i = 0, j = 0;

  

    // Обходим оба массива одновременно

    while (i < n && j < m) {

  

        // Если элемент соответствует

        // увеличиваем оба указателя

        if (A[i] == B[j]) {

  

            i++;

            j++;

  

            // Если массив B полностью

            // пройдено

            if (j == m)

                return true;

        }

        // Если не,

        // увеличиваем i и сбрасываем j

        else {

            i++;

            j = 0;

        }

    }

  

    return false;

}

  
// Код драйвера

int main()

{

    int n = 7, m = 4;

  

    int A[] = { 2, 3, 0, 5, 1, 1, 2 };

    int B[] = { 3, 0, 5, 1 };

  

    if (isSubArray(A, B, n, m))

        cout << "YES\n";

    else

        cout << "NO\n";

  

    return 0;

}

Джава

// Java-программа для проверки, является ли массив
// подмассив другого массива

  

import java.io.*;

  

class GFG {

  

    // Функция для проверки, является ли массив

    // подмассив другого массива

    static boolean isSubArray(int A[], int B[], int n, int m)

    {

        // Два указателя для обхода массивов

        int i = 0, j = 0;

  

        // Обходим оба массива одновременно

        while (i < n && j < m) {

  

            // Если элемент соответствует

            // увеличиваем оба указателя

            if (A[i] == B[j]) {

                i++;

                j++;

  

                // Если массив B полностью

                // пройдено

                if (j == m)

                    return true;

            }

            // Если не,

            // увеличиваем i и сбрасываем j

            else {

                i++;

                j = 0;

            }

        }

  

        return false;

    }

  

    // Код драйвера

  

    public static void main(String[] args)

    {

        int n = 7;

        int m = 4;

  

        int A[] = { 2, 3, 0, 5, 1, 1, 2 };

        int B[] = { 3, 0, 5, 1 };

  

        if (isSubArray(A, B, n, m))

            System.out.println("YES\n");

        else

            System.out.println("NO\n");

    }

}
// Этот код предоставлен shs

python3

# Python 3 программа для проверки наличия массива
# подмассив другого массива

  
# Функция для проверки, является ли массив
# подмассив другого массива

def isSubArray(A, B, n, m):

      

    # Два указателя для обхода массивов

    i = 0

    j = 0

  

    # Обходите оба массива одновременно

    while (i < n and j < m):

          

        # Если элемент соответствует приращению

        # оба указателя

        if (A[i] == B[j]):

            i += 1

            j += 1

  

            # Если массив B полностью

            # пройдено

            if (j == m):

                return True

      

        # Если нет, увеличьте i и сбросьте j

        else:

            i += 1

            j = 0

  

    return False

  
Код водителя

if __name__ == '__main__':

    n = 7

    m = 4

  

    A = [2, 3, 0, 5, 1, 1, 2]

    B = [3, 0, 5, 1]

  

    if (isSubArray(A, B, n, m)):

        print("YES")

    else:

        print("NO")

  
# Этот код предоставлен
# Sanjit_Prasad

C #

// C # программа для проверки наличия массива
// подмассив другого массива

  

using System;

  

class GFG {

  

    // Функция для проверки, является ли массив

    // подмассив другого массива

    static bool isSubArray(int[] A, int[] B, int n, int m)

    {

        // Два указателя для обхода массивов

        int i = 0, j = 0;

  

        // Обходим оба массива одновременно

        while (i < n && j < m) {

  

            // Если элемент соответствует

            // увеличиваем оба указателя

            if (A[i] == B[j]) {

                i++;

                j++;

  

                // Если массив B полностью

                // пройдено

                if (j == m)

                    return true;

            }

            // Если не,

            // увеличиваем i и сбрасываем j

            else {

                i++;

                j = 0;

            }

        }

  

        return false;

    }

  

    // Код драйвера

    static void Main()

    {

        int n = 7;

        int m = 4;

  

        int[] A = { 2, 3, 0, 5, 1, 1, 2 };

        int[] B = { 3, 0, 5, 1 };

  

        if (isSubArray(A, B, n, m))

            Console.WriteLine("YES");

        else

            Console.WriteLine("NO");

    }

    // Этот код предоставлен Ryuga

}

PHP

<?php
// PHP программа для проверки наличия массива
// подмассив другого массива

  
// Функция для проверки, является ли массив
// подмассив другого массива

function isSubArray($A, $B, $n, $m)

{

    // Два указателя для обхода массивов

    $i = $j = 0;

  

    // Обходим оба массива одновременно

    while ($i < $n && $j < $m

    {

  

        // Если элемент соответствует

        // увеличиваем оба указателя

        if ($A[$i] == $B[$j]) 

        {

            $i++;

            $j++;

  

            // Если массив B полностью

            // пройдено

            if ($j == $m)

                return true;

        }

          

        // Если не,

        // увеличиваем i и сбрасываем j

        else 

        {

            $i++;

            $j = 0;

        }

    }

  

    return false;

}

  
// Код драйвера

$n = 7;

$m = 4;

  

$A = array( 2, 3, 0, 5, 1, 1, 2 );

$B = array( 3, 0, 5, 1 );

  

if (isSubArray($A, $B, $n, $m))

    echo "YES\n";

else

    echo "NO\n";

  
// Этот код предоставлен mits
?>

Выход:

YES

Сложность времени : O (N)
Вспомогательное пространство : O (1)

Рекомендуемые посты:

Проверьте, является ли Массив Subarray другого Массива

0.00 (0%) 0 votes