Dada una array arr[] de N enteros distintos , la tarea es verificar si es posible ordenar la array en orden creciente realizando las siguientes operaciones en orden exactamente una vez :
- Dividir la array arr[] en exactamente Y(1 <= Y <= N) subarreglos no vacíos de modo que cada elemento pertenezca exactamente a un subarreglo.
- Reordene los subarreglos en cualquier orden arbitrario.
- Combinar los subarreglos reordenados.
Ejemplos:
Entrada: arr[ ] = {6, 3, 4, 2, 1}, Y = 4
Salida: Sí
Explicación:
Las operaciones se pueden realizar como:
- Divida la array en exactamente 4 subarreglos no vacíos: {6, 3, 4, 2, 1} -> {6}, {3, 4}, {2}, {1}
- Reordenar los subarreglos: {6}, {3, 4}, {2}, {1} -> {1}, {2}, {3, 4}, {6}
- Fusionando los subarreglos: {1}, {2}, {3, 4}, {6} -> {1, 2, 3, 4, 6} ( ordenados )
Entrada: arr[ ] = {1, -4, 0, -2}, Y = 2
Salida: No
Enfoque: la idea principal es que si el número mínimo de divisiones requeridas para ordenar la array dada arr[] es menor o igual que Y, entonces siempre es posible ordenar la array. Además, el número requerido de divisiones debe ser igual al número mínimo de divisiones requeridas para dividir la array en la cantidad mínima de subarreglos no decrecientes .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Initialization of pair
pair<int, int> a[100001];
// Function to check if it is possible
// to sort the array by performing the
// operations exactly once in order
void checkForSortedSubarray(int n, int y, int arr[])
{
// Traversing the array
for (int i = 1; i <= n; i++) {
// Storing the array element
// in the first part of pair
a[i].first = arr[i];
// Storing the index as second
// element in the pair
a[i].second = i;
}
// Initialize Count
int cnt = 1;
// Sorting the array
sort(a + 1, a + n + 1);
for (int i = 1; i <= n - 1; i++) {
// Checking if the index lies
// in order
if (a[i].second != a[i + 1].second - 1)
cnt++;
}
// If minimum splits required is
// greater than y
if (cnt > y)
cout << "No";
else
cout << "Yes";
}
// Driver Code
int main()
{
int Y = 4;
int arr[] = { 6, 3, 4, 2, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
checkForSortedSubarray(N, Y, arr);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Initialization of pair
static pair []a = new pair[100001];
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to check if it is possible
// to sort the array by performing the
// operations exactly once in order
static void checkForSortedSubarray(int n, int y, int arr[])
{
// Traversing the array
for (int i = 1; i <= n; i++) {
// Storing the array element
// in the first part of pair
a[i].first = arr[i];
// Storing the index as second
// element in the pair
a[i].second = i;
}
// Initialize Count
int cnt = 1;
// Sorting the array
Arrays.sort(a,(a, b) -> a.first - b.first);
for (int i = 1; i <= n - 1; i++) {
// Checking if the index lies
// in order
if (a[i].second != a[i + 1].second - 1)
cnt++;
}
// If minimum splits required is
// greater than y
if (cnt > y)
System.out.print("No");
else
System.out.print("Yes");
}
// Driver Code
public static void main(String[] args)
{
int Y = 4;
int arr[] = { 6, 3, 4, 2, 1 };
int N = arr.length;
for(int i = 0;i<a.length;i++) {
a[i] = new pair(0, 0);
}
checkForSortedSubarray(N-1, Y, arr);
}
}
// This code is contributed by Princi Singh
Python3
# Python 3 program for the above approach
# Initialization of pair
# Function to check if it is possible
# to sort the array by performing the
# operations exactly once in order
def checkForSortedSubarray(n, y, arr, a):
# Traversing the array
for i in range(0, n, 1):
# Storing the array element
# in the first part of pair
a[i][0] = arr[i]
# Storing the index as second
# element in the pair
a[i][1] = i
# Initialize Count
cnt = 1
# Sorting the array
a.sort()
for i in range(0,n,1):
# Checking if the index lies
# in order
if (a[i][1] != a[i + 1][1] - 1):
cnt += 1
# If minimum splits required is
# greater than y
if (cnt > y):
print("Yes")
else:
print("No")
# Driver Code
if __name__ == '__main__':
Y = 4
a = [[0,0] for i in range(100001)]
arr = [6, 3, 4, 2, 1]
N = len(arr)
checkForSortedSubarray(N, Y, arr,a)
# This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
// Initialization of pair
static List<pair> a = new List<pair>();
public class pair {
public int first, second;
public pair(int first, int second) {
this.first = first;
this.second = second;
}
}
// Function to check if it is possible
// to sort the array by performing the
// operations exactly once in order
static void checkForSortedSubarray(int n, int y, int []arr) {
// Traversing the array
for (int i = 1; i <= n; i++)
{
// Storing the array element
// in the first part of pair
a[i].first = arr[i];
// Storing the index as second
// element in the pair
a[i].second = i;
}
// Initialize Count
int cnt = 1;
// Sorting the array
a.Sort((c, b) => c.first - b.first);
for (int i = 1; i <= n - 1; i++) {
// Checking if the index lies
// in order
if (a[i].second != a[i + 1].second - 1)
cnt++;
}
// If minimum splits required is
// greater than y
if (cnt > y)
Console.Write("No");
else
Console.Write("Yes");
}
// Driver Code
public static void Main(String[] args)
{
int Y = 4;
int []arr = { 6, 3, 4, 2, 1 };
int N = arr.Length;
for (int i = 0; i < 100001; i++) {
a.Add(new pair(0, 0));
}
checkForSortedSubarray(N - 1, Y, arr);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to check if it is possible
// to sort the array by performing the
// operations exactly once in order
// Initialization of pair
var a = [];
function checkForSortedSubarray(n, y, arr)
{
// Traversing the array
for (let i = 0; i < n; i++)
{
// Storing the array element
// in the first part of pair
// Storing the index as second
// element in the pair
a.push({
first: arr[i],
second: i
})
}
// Initialize Count
let cnt = 1;
// Sorting the array
a.sort(function (a, b) { return a.first - b.first; })
for (let i = 0; i < n - 1; i++) {
// Checking if the index lies
// in order
if (a[i].second != a[i + 1].second - 1)
cnt++;
}
// If minimum splits required is
// greater than y
if (cnt > y)
document.write("No");
else
document.write("Yes");
}
// Driver Code
let Y = 4;
let arr = [6, 3, 4, 2, 1];
let N = arr.length;
checkForSortedSubarray(N, Y, arr);
// This code is contributed by Potta Lokesh
</script>
Producción
Yes
Complejidad temporal: O(N Log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por laraibanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA