Verifique si Array se puede ordenar en orden no decreciente usando operaciones dadas

Dada una array arr[] de tamaño N que consta de enteros positivos, la tarea es verificar si la array se puede ordenar en orden no decreciente realizando las siguientes operaciones:

• Seleccione dos elementos adyacentes.
• Intercambia los elementos e invierte sus signos.
• Todos los elementos de la array ordenada recibida al final deben ser positivos.

Ejemplo:

Entrada: N = 4, arr[] = [4, 3, 2, 5]
Salida: verdadero
Explicación: En la array dada, realice las siguientes operaciones:
Intercambiar arr[0] y arr[1] array actualizada: [-3 , -4, 2, 5]
Intercambiar arr[1] y arr[2] array actualizada: [-3, -2, 4, 5]
Intercambiar arr[1] y arr[0] array actualizada: [2, 3, 4, 5]
La array está ordenada en orden no decreciente y todos los elementos son positivos.

Entrada: N = 4, arr[] = [3, 3, 2, 2]
Salida: verdadero
Explicación: En la array dada, realice las siguientes operaciones:
Intercambiar arr[0] y arr[2] array actualizada: [-2 , 3, -3, 2]
Intercambiar arr[1] y arr[3] array actualizada: [-2, -2, -3, -3]
Intercambiar arr[1] y arr[0] array actualizada: [2, 2, -3, -3]
Intercambiar arr[2] y arr[3] array actualizada: [2, 2, 3, 3]
La array está ordenada en orden no decreciente y todos los elementos son positivos.

Entrada: N = 5, arr[] = [1, 2, 3, 5, 4]
Salida: falso
Explicación:  No hay forma de ordenar la array de modo que cumpla todas las condiciones mencionadas.

Enfoque: El problema se puede resolver usando el enfoque Greedy basado en la siguiente observación:

Cada número debe moverse una distancia uniforme porque todos deben ser positivos al final. Y un número positivo sigue siendo positivo solo después de un número par de inversión de signos.
Entonces, la diferencia de distancia para todos los elementos de la array entre el dado y la array ordenada debe ser par.

Siga los pasos a continuación para resolver este problema:

• Inicialice un mapa vacío (por ejemplo, ctr[2][] ) para mantener la frecuencia de un elemento de array en una posición par y en una posición impar.
• Iterar sobre una array arr e incrementar el ctr[i % 1][arr[i]] en 1 
• Ordene la array arr[] .
• Iterar sobre la array arr[] y disminuir ctr[i % 1][arr[i]] en 1.
• Iterar sobre la array arr[] y si ctr[1][a[i]] ≠ 0 o ctr[0][a[i]] ≠ 0 entonces devuelve false.
• De lo contrario, si la iteración está completa, devuelve verdadero.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find if it is possible
// to sort the array in non-decreasing order
bool isItPossible(int n, vector<int>& a)
{
    // Initializing a map 'ctr'.
    map<int, int> ctr[2];
 
    // Iterating over an array and updating
    // the count for each occurrence
    for (int i = 0; i < n; i++) {
        ctr[i % 2][a[i]]++;
    }
 
    // Sorting out the array
    sort(a.begin(), a.end());
 
    // Updating count again according the
    // sorted array
    for (int i = 0; i < n; i++) {
        ctr[i % 2][a[i]]--;
    }
 
    // Iterating over array again and if the
    // count is not zero then returning false
    for (int i = 0; i < n; i++) {
        if (ctr[0][a[i]] != 0 || ctr[1][a[i]] != 0) {
            return false;
        }
    }
    return true;
}
 
// Driver code
int main()
{
    int N = 4;
    vector<int> arr = { 3, 3, 2, 2 };
 
    // Function call
    cout << boolalpha
         << isItPossible(N, arr);
    return 0;
}

// Java program for above approach
import java.util.*;
 
class GFG
{
   
    // Function to find if it is possible
    // to sort the array in non-decreasing order
    public static boolean isItPossible(int n, int[] a)
    {
       
        // Initializing 2 maps 'ctr1' and 'ctr2'
        Map<Integer, Integer> ctr1 = new HashMap<Integer, Integer>();
        Map<Integer, Integer> ctr2 = new HashMap<Integer, Integer>();
       
        // Iterating over an array and updating
        // the count for each occurrence
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0)
            {
                if (ctr1.containsKey(a[i]))
                    ctr1.put(a[i], ctr1.get(a[i]) + 1);
                else
                    ctr1.put(a[i], 1);
            }
            else
            {
                if (ctr2.containsKey(a[i]))
                    ctr2.put(a[i], ctr2.get(a[i]) + 1);
                else
                    ctr2.put(a[i], 1);
            }
        }
     
        // Sorting out the array
        Arrays.sort(a);
     
        // Updating count again according the
        // sorted array
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0)
            {
                if (ctr1.containsKey(a[i]))
                    ctr1.put(a[i], ctr1.get(a[i]) - 1);
                else
                    ctr1.put(a[i],  -1);
            }
            else
            {
                if (ctr2.containsKey(a[i]))
                    ctr2.put(a[i], ctr2.get(a[i]) - 1);
                else
                    ctr2.put(a[i],  -1);
            }
        }
     
        // Iterating over array again and if the
        // count is not zero then returning false
        for (int i = 0; i < n; i++) {
            if (ctr1.get(a[i]) != 0 || ctr2.get(a[i]) != 0) {
                return false;
            }
        }
        return true;
    }
 
    public static void main(String[] args) {
        int N = 4;
        int[] arr = { 3, 3, 2, 2 };
     
        // Function call
        System.out.println(isItPossible(N, arr));
    }
}
 
// This code is contributed by phasing17

# Python3 code for the above approach
 
# Function to find if it is possible
# to sort the array in non-decreasing order
def isItPossible(n, a):
 
    # Initializing a list of dicts 'ctr'.
    ctr = [dict(), dict()]
 
    # Iterating over an array and updating
    # the count for each occurrence
    for i in range(n):
        if a[i] in ctr[i % 2]:
            ctr[i % 2][a[i]] += 1
        else:
            ctr[i % 2][a[i]] = 1
 
    # sorting the array
    a.sort()
 
    # updating count again according
    # to the sorted array
    for i in range(n):
        if a[i] in ctr[i % 2]:
            ctr[i % 2][a[i]] -= 1
 
    # iterating over array again
    # and if the count is not zero
    # then returning false
    for i in range(n):
        if a[i] in ctr[0] and ctr[0][a[i]] != 0 or a[i] in ctr[1] and ctr[1][a[i]] != 0:
            return False
 
    return True
 
# Driver Code
N = 4
arr = [3, 3, 2, 2]
 
# Function Call
print(isItPossible(N, arr))
 
# This code is contributed by phasing17

// C# program for above approach
 
// Include namespace system
using System;
using System.Collections.Generic;
using System.Linq;
using System.Collections;
 
public class GFG
{
   
    // Function to find if it is possible
    // to sort the array in non-decreasing order
    public static bool isItPossible(int n, int[] a)
    {
       
        // Initializing 2 maps 'ctr1' and 'ctr2'
        var ctr1 = new Dictionary<int, int>();
        var ctr2 = new Dictionary<int, int>();
       
        // Iterating over an array and updating
        // the count for each occurrence
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                if (ctr1.ContainsKey(a[i])) {
                    ctr1[a[i]] = ctr1[a[i]] + 1;
                }
                else {
                    ctr1[a[i]] = 1;
                }
            }
            else {
                if (ctr2.ContainsKey(a[i])) {
                    ctr2[a[i]] = ctr2[a[i]] + 1;
                }
                else {
                    ctr2[a[i]] = 1;
                }
            }
        }
       
        // Sorting out the array
        Array.Sort(a);
       
        // Updating count again according the
        // sorted array
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                if (ctr1.ContainsKey(a[i])) {
                    ctr1[a[i]] = ctr1[a[i]] - 1;
                }
                else {
                    ctr1[a[i]] = -1;
                }
            }
            else {
                if (ctr2.ContainsKey(a[i])) {
                    ctr2[a[i]] = ctr2[a[i]] - 1;
                }
                else {
                    ctr2[a[i]] = -1;
                }
            }
        }
       
        // Iterating over array again and if the
        // count is not zero then returning false
        for (int i = 0; i < n; i++) {
            if (ctr1[a[i]] != 0 || ctr2[a[i]] != 0) {
                return false;
            }
        }
        return true;
    }
    public static void Main(String[] args)
    {
        var N = 4;
        int[] arr = { 3, 3, 2, 2 };
       
        // Function call
        Console.WriteLine(GFG.isItPossible(N, arr));
    }
}
 
 // This code is contributed by mukulsomukesh

    <script>
        // JavaScript program for above approach
 
        // Function to find if it is possible
        // to sort the array in non-decreasing order
        const isItPossible = (n, a) => {
         
            // Initializing a map 'ctr'.
            let ctr = [{}, {}];
 
            // Iterating over an array and updating
            // the count for each occurrence
            for (let i = 0; i < n; i++) {
                ctr[i % 2][a[i]] = a[i] in ctr[i % 2] ? ctr[i % 2][a[i]] + 1 : 1;
            }
             
            // Sorting out the array
            a.sort();
 
            // Updating count again according the
            // sorted array
            for (let i = 0; i < n; i++) {
                if (a[i] in ctr[i % 2])
                    ctr[i % 2][a[i]]--;
            }
             
            // Iterating over array again and if the
            // count is not zero then returning false
            for (let i = 0; i < n; i++) {
                if (a[i] in ctr[0] && ctr[0][a[i]] != 0 || a[i] in ctr[1] && ctr[1][a[i]] != 0) {
                    return false;
                }
            }
            return true;
        }
 
        // Driver code
 
        let N = 4;
        let arr = [3, 3, 2, 2];
s
        // Function call
        document.write(isItPossible(N, arr));
 
    // This code is contributed by rakeshsahni
 
    </script>

true

Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(N)