Проверьте, может ли массив располагаться в левом или правом позиционированном массиве

31.12.2019Массивы

Для заданного массива arr [] размера n> 4 задача состоит в том, чтобы проверить, можно ли упорядочить данный массив в виде левого или правого массива?
Левый или правый позиционированный массив означает, что каждый элемент в массиве равен количеству элементов слева или количеству элементов справа.

Примеры :

Input  : arr[] = {1, 3, 3, 2}
Output : "YES"  
This array has one such arrangement {3, 1, 2, 3}. 
In this arrangement, first element '3' indicates 
that three numbers are after it, the 2nd element 
'1' indicates that one number is before it, the 
3rd element '2' indicates that two elements are 
before it.

Input : arr[] = {1, 6, 5, 4, 3, 2, 1}
Output: "NO"
// No such arrangement is possible

Input : arr[] = {2, 0, 1, 3}
Output: "YES"
// Possible arrangement is {0, 1, 2, 3}

Input : arr[] = {2, 1, 5, 2, 1, 5}
Output: "YES"
// Possible arrangement is {5, 1, 2, 2, 1, 5}

Простое решение состоит в том, чтобы сгенерировать все возможные схемы размещения (см. Эту статью) и проверить условие расположения массива влево или вправо, если каждый элемент в массиве удовлетворяет условию, то «YES» или «NO». Временная сложность для этого подхода составляет O (n * n! + N), n * n! сгенерировать все договоренности и n для проверки состояния с использованием временного массива.

Эффективное решение этой проблемы требует небольшого наблюдения и бумажной работы. Чтобы удовлетворить условию левого или правого позиционированного массива, все числа в массиве должны быть равны index, i или (n-1-i) и arr [i] <n. Таким образом, мы создаем массив посещенных [] размером n и инициализируем его элемент с 0. Затем мы пересекаем массив и выполняем следующие шаги:

Если он посещен [arr [i]] = 0, тогда задайте 1, что проверяет условие, что количество элементов в левой части массива arr [0]… arr [i-1] равно arr [i].
Иначе make make [n-arr [i] -1] = 1, которая проверяет условие, что число элементов в правой части массива arr [i + 1]… arr [n-1] равно arr [i ].
Теперь переходим в массив посещенных [], и если все элементы массива посещенных [] становятся равными 1, это означает, что расположение возможно «ДА», иначе «НЕТ».

C ++

// C ++ программа для проверки возможности размещения массива
// к левому или правому позиционированному массиву.
#include<bits/stdc++.h>

using namespace std;

// Функция для проверки влево или вправо
// Массив.
// arr [] это массив из n элементов
// visit [] - логический массив размера n

bool leftRight(int arr[],int n)

{

// Первоначально ни один элемент не размещен в любой позиции

int visited[n] = {0};

// Обход каждого элемента массива

for (int i=0; i<n; i++)

{

// Элемент должен быть меньше чем n.

if (arr[i] < n)

{

// Поместить "arr [i]" в позицию "i"

// или в позиции n-arr [i] -1

if (visited[arr[i]] == 0)

visited[arr[i]] = 1;

else

visited[n-arr[i]-1] = 1;

}

// Все позиции должны быть заняты

for (int i=0; i<n; i++)

if (visited[i] == 0)

return false;

return true;

}

// Драйвер программы для проверки кейса

int main()

{

int arr[] = {2, 1, 5, 2, 1, 5};

int n = sizeof(arr)/sizeof(arr[0]);

if (leftRight(arr, n) == true)

cout << "YES";

else

cout << "NO";

return 0;

}

Джава

// Java-программа для проверки наличия массива
// можно расположить слева или
// правый массив.

class GFG {

// Функция для проверки влево или

// Правильно расположенный массив.

// arr [] это массив из n элементов

// visit [] - логический массив размера n

static boolean leftRight(int arr[], int n) {

// изначально нет элемента

// помещаем в любую позицию

int visited[] = new int[n];

// Обход каждого элемента массива

for (int i = 0; i < n; i++) {

// Элемент должен быть меньше чем n.

if (arr[i] < n) {

// Поместить "arr [i]" в позицию "i"

// или в позиции n-arr [i] -1

if (visited[arr[i]] == 0)

visited[arr[i]] = 1;

else

visited[n - arr[i] - 1] = 1;

}

// Все позиции должны быть заняты

for (int i = 0; i < n; i++)

if (visited[i] == 0)

return false;

return true;

}

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

public static void main(String[] args)

{

int arr[] = {2, 1, 5, 2, 1, 5};

int n = arr.length;

if (leftRight(arr, n) == true)

System.out.print("YES");

else

System.out.print("NO");

}
}

// Этот код предоставлен Anant Agarwal.

python3

# Python3 программа для проверки
# если массив может быть организован
# к левому или правому позиционированному массиву.

# Функция для проверки слева
# или вправо
# Массив.
# arr [] - массив из n элементов
# visit [] - логический массив размера n

def leftRight(arr,n):

# Изначально нет элемента

# находится в любой позиции

visited=[]

for i in range(n+1):

visited.append(0)

# Обходить каждый элемент массива

for i in range(n):

# Элемент должен быть меньше чем n.

if (arr[i] < n):

# Поместите "arr [i]" в положение "i"

# или в позиции n-arr [i] -1

if (visited[arr[i]] == 0):

visited[arr[i]] = 1

else:

visited[n-arr[i]-1] = 1

# Все позиции должны быть заняты

for i in range(n):

if (visited[i] == 0):

return False

return True

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

arr = [2, 1, 5, 2, 1, 5]

n = len(arr)

if (leftRight(arr, n) == True):

print("YES")

else:

print("NO")

# Этот код добавлен
# Анант Агарвал.

C #

// C # программа для проверки наличия массива
// можно расположить слева или
// правый массив.

using System;

public class GFG {

// Функция для проверки влево или

// Правильно расположенный массив.

// arr [] это массив из n элементов

// visit [] - логический массив размера n

static bool leftRight(int []arr, int n) {

// изначально нет элемента

// помещаем в любую позицию

int []visited = new int[n];

// Обход каждого элемента массива

for (int i = 0; i < n; i++) {

// Элемент должен быть меньше чем n.

if (arr[i] < n) {

// Поместить "arr [i]" в позицию "i"

// или в позиции n-arr [i] -1

if (visited[arr[i]] == 0)

visited[arr[i]] = 1;

else

visited[n - arr[i] - 1] = 1;

}

// Все позиции должны быть заняты

for (int i = 0; i < n; i++)

if (visited[i] == 0)

return false;

return true;

}

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

public static void Main()

{

int []arr = {2, 1, 5, 2, 1, 5};

int n = arr.Length;

if (leftRight(arr, n) == true)

Console.WriteLine("YES");

else

Console.WriteLine("NO");

}

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

PHP

<?php
// PHP программа для проверки
// массив может быть организован в
// левый или правый позиционированный массив.

// Функция для проверки влево или
// Правильно расположенный массив.
// arr [] это массив из n элементов
// visit [] - логический массив размера n

function leftRight($arr, $n)

{

// изначально нет элемента

// помещаем в любую позицию

$visited[$n] = array(0);

// Обход каждого элемента массива

for ($i = 0; $i < $n; $i++)

{

// Элемент должен быть меньше чем n.

if ($arr[$i] < $n)

{

// Поместить "arr [i]" в позицию "i"

// или в позиции n-arr [i] -1

$visited[$arr[$i]] = 1;

$visited[$n - $arr[$i] - 1] = 1;

}

// Все позиции должны быть заняты

for ($i = 0; $i < $n; $i++)

if ($visited[$i] == 0)

return false;

return true;

}

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

$arr = array(2, 1, 5, 2, 1, 5);

$n = sizeof($arr);

if (leftRight($arr, $n) == true)

echo "YES";

else

echo "NO";

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

Выход :

"YES"

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

Эта статья предоставлена Шашанком Мишрой (Гуллу) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Проверьте, может ли массив располагаться в левом или правом позиционированном массиве

0.00 (0%) 0 votes