Dada una array arr[] de longitud N y otra array P[] que contiene {a 1 , a 2 , … ak } que representa las posiciones de la array dada arr[], la tarea es verificar si la array se puede ordenar simplemente intercambiando los elementos arr[a i ], arr[a i+1 ] donde ‘i’ es algún elemento en la array P[].
Ejemplos:
Entrada: arr[] = {3, 2, 1}, P[] = {1, 2}
Salida: Sí
Explicación:
Inicialmente, i = 1 (es decir) se intercambian el primer elemento y el segundo elemento. Por lo tanto, arr[0] <=> arr[1]. array[] = {2, 3, 1}.
De manera similar, i = 2 (es decir) se intercambian el segundo elemento y el tercer elemento. array[] = {2, 1, 3}.
Finalmente, i = 1 (es decir) se intercambian el primer elemento y el segundo elemento. array[] = {1, 2, 3}.
Dado que esta array está ordenada, por lo tanto, la array dada puede ordenarse.
Entrada: arr[] = {5, 3, -4, 1, 12}, P[] = {2, 4, 3}
Salida: No
Enfoque : la idea es utilizar un enfoque de dos punteros para verificar si la array se puede ordenar o no.
- Inicialmente, creamos una array de posición pos[] de tamaño N. Esta array se utilizará para marcar las posiciones dadas en la array P[] . Eso es:
if j = ai (1 ≤ i ≤ K) then the element pos[ai-1] will be 1 else 0
- Ahora, itere a través de la array y verifique si pos[i] = 1 o no.
- Si encontramos el pos[i]=1 , almacenamos el iterador en una variable temporal, y luego incrementamos el iterador con el valor 1 , hasta que tengamos pos[i]=1 continuamente, es decir,
j = i
while (j < N and pos[j])
j=j+1
- Después de este incremento, ordenamos este segmento que obtuvimos de i a j+1 y finalmente, comprobamos después de la posición j, en el vector que tenemos que comprobar, porque hemos ordenado hasta este segmento.
Sort(arr[i] to arr[j+1]) i=j
- Finalmente, después de completar este ciclo, debemos verificar si la array se ha ordenado o no.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if the array
// can be sorted only if the elements
// on the given positions can be swapped
#include <bits/stdc++.h>
using namespace std;
// Function to check if the array can
// be sorted only if the elements on
// the given positions can be swapped
void check_vector(vector<int> A, int n,
vector<int> p)
{
// Creating an array for marking
// the positions
vector<int> pos(A.size());
// Iterating through the array and
// mark the positions
for (int i = 0; i < p.size(); i++) {
pos[p[i] - 1] = 1;
}
int flag = 1;
// Iterating through the given array
for (int i = 0; i < n; i++) {
if (pos[i] == 0)
continue;
int j = i;
// If pos[i] is 1, then incrementing
// till 1 is continuously present in pos
while (j < n && pos[j])
++j;
// Sorting the required segment
sort(A.begin() + i, A.begin() + j + 1);
i = j;
}
// Checking if the vector is sorted or not
for (int i = 0; i < n - 1; i++) {
if (A[i] > A[i + 1]) {
flag = 0;
break;
}
}
// Print yes if it is sorted
if (flag == 1)
cout << "Yes";
else
cout << "No";
}
// Driver code
int main()
{
vector<int> A{ 3, 2, 1 };
vector<int> p{ 1, 2 };
check_vector(A, A.size(), p);
return 0;
}
Java
// Java program to check if the array
// can be sorted only if the elements
// on the given positions can be swapped
import java.util.Arrays;
class GFG{
// Function to check if the array can
// be sorted only if the elements on
// the given positions can be swapped
public static void check_vector(int[] A,
int n,
int[] p)
{
// Creating an array for marking
// the positions
int[] pos = new int[A.length];
// Iterating through the array and
// mark the positions
for(int i = 0; i < p.length; i++)
{
pos[p[i] - 1] = 1;
}
int flag = 1;
// Iterating through the given array
for(int i = 0; i < n; i++)
{
if (pos[i] == 0)
continue;
int j = i;
// If pos[i] is 1, then incrementing
// till 1 is continuously present in pos
while (j < n && pos[j] != 0)
++j;
// Sorting the required segment
Arrays.sort(A, i, j + 1);
i = j;
}
// Checking if the vector is sorted or not
for(int i = 0; i < n - 1; i++)
{
if (A[i] > A[i + 1])
{
flag = 0;
break;
}
}
// Print yes if it is sorted
if (flag == 1)
System.out.print("Yes");
else
System.out.print("No");
}
// Driver code
public static void main(String[] args)
{
int A[] = { 3, 2, 1 };
int p[] = { 1, 2 };
check_vector(A, A.length, p);
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program to check if the array
# can be sorted only if the elements
# on the given positions can be swapped
# Function to check if the array can
# be sorted only if the elements on
# the given positions can be swapped
def check_vector(A, n, p):
# Creating an array for marking
# the positions
pos = [0 for i in range(len(A))]
# Iterating through the array and
# mark the positions
for i in range(len(p)):
pos[p[i] - 1] = 1
flag = 1
# Iterating through the given array
for i in range(n):
if (pos[i] == 0):
continue
j = i
# If pos[i] is 1, then incrementing
# till 1 is continuously present in pos
while (j < n and pos[j]):
j += 1
# Sorting the required segment
p = A[: i]
q = A[i : i + j + 1]
r = A[i + j + 1 : len(A)]
q.sort(reverse = False)
A = p + q + r
i = j
# Checking if the vector is sorted or not
for i in range(n - 1):
if (A[i] > A[i + 1]):
flag = 0
break
# Print yes if it is sorted
if (flag == 1):
print("Yes")
else:
print("No");
# Driver code
if __name__ == '__main__':
A = [ 3, 2, 1 ]
p = [ 1, 2 ]
check_vector(A,len(A), p)
# This code is contributed by Samarth
C#
// C# program to check
// if the array can be
// sorted only if the
// elements on the given
// positions can be swapped
using System;
class GFG{
// Function to check if the array can
// be sorted only if the elements on
// the given positions can be swapped
public static void check_vector(int[] A,
int n,
int[] p)
{
// Creating an array for marking
// the positions
int[] pos = new int[A.Length];
// Iterating through the array and
// mark the positions
for(int i = 0; i < p.Length; i++)
{
pos[p[i] - 1] = 1;
}
int flag = 1;
// Iterating through the given array
for(int i = 0; i < n; i++)
{
if (pos[i] == 0)
continue;
int j = i;
// If pos[i] is 1, then
// incrementing till 1
// is continuously present in pos
while (j < n && pos[j] != 0)
++j;
// Sorting the required segment
Array.Sort(A, i, j + 1);
i = j;
}
// Checking if the vector
// is sorted or not
for(int i = 0; i < n - 1; i++)
{
if (A[i] > A[i + 1])
{
flag = 0;
break;
}
}
// Print yes if it is sorted
if (flag == 1)
Console.Write("Yes");
else
Console.Write("No");
}
// Driver code
public static void Main()
{
int[] A = {3, 2, 1};
int[] p = {1, 2};
check_vector(A, A.Length, p);
}
}
// This code is contributed by Chitranayal
Javascript
<script>
// Javascript program to check if the array
// can be sorted only if the elements
// on the given positions can be swapped
// Function to check if the array can
// be sorted only if the elements on
// the given positions can be swapped
function check_vector(A, n, p)
{
// Creating an array for marking
// the positions
var pos = A.length;
// Iterating through the array and
// mark the positions
for (var i = 0; i < p.length; i++) {
pos[p[i] - 1] = 1;
}
var flag = 1;
// Iterating through the given array
for (var i = 0; i < n; i++) {
if (pos[i] == 0)
continue;
var j = i;
// If pos[i] is 1, then incrementing
// till 1 is continuously present in pos
while (j < n && pos[j])
++j;
// Sorting the required segment
A = Array.prototype.concat(
A.slice(0, i),
A.slice(i+1, j+1).sort((a,b)=>a-b),
A.slice(j+2).sort((a,b)=>a-b));
i = j;
}
// Checking if the vector is sorted or not
for (var i = 0; i < n - 1; i++) {
if (A[i] > A[i + 1]) {
flag = 0;
break;
}
}
// Print yes if it is sorted
if (flag == 1)
document.write( "Yes");
else
document.write( "No");
}
// Driver code
var A = [ 3, 2, 1 ];
var p = [ 1, 2 ];
check_vector(A, A.length, p);
// This code is contributed by noob2000.
</script>
Producción:
Yes
Complejidad de tiempo: O(N * log(N)) , donde N es el tamaño de la array.
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA