Dada una array de números positivos y negativos, organícelos de manera que todos los enteros negativos aparezcan antes que todos los enteros positivos en la array sin usar ninguna estructura de datos adicional como tabla hash, arrays, etc. Se debe mantener el orden de aparición.
Ejemplos:
Input: [12 11 -13 -5 6 -7 5 -3 -6] Output: [-13 -5 -7 -3 -6 12 11 6 5]
Una solución simple es usar otra array. Copiamos todos los elementos de la array original a una nueva array. Luego recorremos la nueva array y copiamos todos los elementos negativos y positivos nuevamente en la array original uno por uno. Este enfoque es discutido . El problema con este enfoque es que usa una array auxiliar y no se nos permite usar ninguna estructura de datos para resolver este problema.
Un enfoque que no usa ninguna estructura de datos es usar el proceso de partición de QuickSort. La idea es considerar el 0 como un pivote y dividir el arreglo a su alrededor. El problema con este enfoque es que cambia el orden relativo de los elementos. Aquí se analiza un proceso de partición similar .
Analicemos ahora algunos métodos que no usan ninguna otra estructura de datos y también preservan el orden relativo de los elementos.
Enfoque 1: proceso de partición modificado de clasificación rápida
Podemos invertir el orden de los números positivos siempre que se cambie el orden relativo. Esto sucederá si hay más de un elemento positivo entre el último número negativo en el subarreglo izquierdo y el elemento negativo actual.
A continuación se muestran los pasos sobre cómo sucederá esto:
Current Array :- [Ln, P1, P2, P3, N1, .......]
Here, Ln is the left subarray(can be empty) that contains only negative elements. P1, P2, P3 are the positive numbers and N1
is the negative number that we want to move at correct place.
If difference of indices between positive number and negative number is greater than 1,
1. Swap P1 and N1, we get [Ln, N1, P2, P3, P1, ......]
2. Rotate array by one position to right, i.e. rotate array [P2, P3, P1], we get [Ln, N1, P1, P2, P3, ......]
A continuación se muestra la implementación de la misma de la siguiente manera:
C++
// C++ program to Rearrange positive and negative
// numbers in a array
#include <bits/stdc++.h>
using namespace std;
// A utility function to print an array of size n
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout<<arr[i]<<" ";
}
void rotateSubArray(int arr[], int l, int r) {
int temp = arr[r];
for (int j = r; j > l - 1; j--) {
arr[j] = arr[j - 1];
}
arr[l] = temp;
}
void moveNegative(int arr[], int n)
{
int last_negative_index = -1;
for (int i = 0; i < n; i++) {
if (arr[i] < 0) {
last_negative_index += 1;
int temp = arr[i];
arr[i] = arr[last_negative_index];
arr[last_negative_index] = temp;
// Done to manage order too
if (i - last_negative_index >= 2)
rotateSubArray(arr, last_negative_index + 1, i);
}
}
}
// Driver Code
int main()
{
int arr[] = { 5, 5, -3, 4, -8, 0, -7, 3, -9, -3, 9, -2, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
moveNegative(arr, n);
printArray(arr, n);
return 0;
}
// This code is contributed by Aarti_Rathi
Java
// Java program for
// moving negative numbers to left
// while maintaining the order
class GFG {
static int[] rotateSubArray(int[] arr, int l, int r) {
int temp = arr[r];
for (int j = r; j > l - 1; j--) {
arr[j] = arr[j - 1];
}
arr[l] = temp;
return arr;
}
static int[] moveNegative(int[] arr) {
int last_negative_index = -1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] < 0) {
last_negative_index += 1;
int temp = arr[i];
arr[i] = arr[last_negative_index];
arr[last_negative_index] = temp;
// Done to manage order too
if (i - last_negative_index >= 2)
rotateSubArray(arr, last_negative_index + 1, i);
}
}
return arr;
}
// Driver Code
public static void main(String args[]) {
int[] arr = { 5, 5, -3, 4, -8, 0, -7, 3, -9, -3, 9, -2, 1 };
arr = moveNegative(arr);
for (int i : arr) {
System.out.print(i + " ");
}
}
}
// This code is contributed by Saurabh Jaiswal
Python3
# Python 3 program for # moving negative numbers to left # while maintaining the order class Solution: def rotateSubArray(self, arr, l, r): temp = arr[r] for j in range(r, l-1, -1): arr[j] = arr[j-1] arr[l] = temp return arr def moveNegative(self, arr): last_negative_index = -1 for i in range(len(arr)): if arr[i] < 0: last_negative_index += 1 arr[i], arr[last_negative_index] = arr[last_negative_index], arr[i] # Done to manage order too if i - last_negative_index >= 2: self.rotateSubArray(arr, last_negative_index+1, i) return arr # Driver Code if __name__ == '__main__': arr = [5, 5, -3, 4, -8, 0, -7, 3, -9, -3, 9, -2, 1] ob = Solution() ob.moveNegative(arr) for i in arr: print(i, end=' ') print() # This code is contributed by Kapil Bansal(devkapilbansal)
C#
// C# program for
// moving negative numbers to left
// while maintaining the order
using System;
class GFG {
static int[] rotateSubArray(int[] arr, int l, int r) {
int temp = arr[r];
for (int j = r; j > l - 1; j--) {
arr[j] = arr[j - 1];
}
arr[l] = temp;
return arr;
}
static int[] moveNegative(int[] arr) {
int last_negative_index = -1;
for (int i = 0; i < arr.Length; i++) {
if (arr[i] < 0) {
last_negative_index += 1;
int temp = arr[i];
arr[i] = arr[last_negative_index];
arr[last_negative_index] = temp;
// Done to manage order too
if (i - last_negative_index >= 2)
rotateSubArray(arr, last_negative_index + 1, i);
}
}
return arr;
}
// Driver Code
public static void Main() {
int[] arr = { 5, 5, -3, 4, -8, 0, -7, 3, -9, -3, 9, -2, 1 };
arr = moveNegative(arr);
foreach (int i in arr) {
Console.Write(i + " ");
}
}
}
// This code is contributed by gfgking.
Javascript
<script>
// Python 3 program for
// moving negative numbers to left
// while maintaining the order
class Solution{
rotateSubArray(arr, l, r){
let temp = arr[r]
for(let j = r;j > l-1;j--){
arr[j] = arr[j-1]
}
arr[l] = temp
return arr
}
moveNegative(arr){
let last_negative_index = -1
for(let i=0;i<arr.length;i++){
if(arr[i] < 0){
last_negative_index += 1
let temp = arr[i];
arr[i] = arr[last_negative_index];
arr[last_negative_index] = temp;
// Done to manage order too
if(i - last_negative_index >= 2)
this.rotateSubArray(arr, last_negative_index+1, i)
}
}
return arr
}
}
// Driver Code
let arr = [5, 5, -3, 4, -8, 0, -7, 3, -9, -3, 9, -2, 1]
let ob = new Solution()
ob.moveNegative(arr)
for(let i of arr){
document.write(i,' ')
}
// This code is contributed by shinjanpatra
</script>
Producción
-3 -8 -7 -9 -3 -2 5 5 4 0 3 9 1
Complejidad de tiempo: O(n)
Complejidad espacial: O(1)
Enfoque 2: Clasificación por inserción modificada
Podemos modificar el ordenamiento por inserción para resolver este problema.
Algoritmo:
Loop from i = 1 to n - 1.
a) If the current element is positive, do nothing.
b) If the current element arr[i] is negative, we
insert it into sequence arr[0..i-1] such that
all positive elements in arr[0..i-1] are shifted
one position to their right and arr[i] is inserted
at index of first positive element.
A continuación se muestra la implementación:
C++
// C++ program to Rearrange positive and negative
// numbers in a array
#include <stdio.h>
// A utility function to print an array of size n
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Function to Rearrange positive and negative
// numbers in a array
void RearrangePosNeg(int arr[], int n)
{
int key, j;
for (int i = 1; i < n; i++) {
key = arr[i];
// if current element is positive
// do nothing
if (key > 0)
continue;
/* if current element is negative,
shift positive elements of arr[0..i-1],
to one position to their right */
j = i - 1;
while (j >= 0 && arr[j] > 0) {
arr[j + 1] = arr[j];
j = j - 1;
}
// Put negative element at its right position
arr[j + 1] = key;
}
}
/* Driver program to test above functions */
int main()
{
int arr[] = { -12, 11, -13, -5, 6, -7, 5, -3, -6 };
int n = sizeof(arr) / sizeof(arr[0]);
RearrangePosNeg(arr, n);
printArray(arr, n);
return 0;
}
Java
// Java program to Rearrange positive
// and negative numbers in a array
import java.io.*;
class GFG {
// A utility function to print
// an array of size n
static void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
// Function to Rearrange positive and negative
// numbers in a array
static void RearrangePosNeg(int arr[], int n)
{
int key, j;
for (int i = 1; i < n; i++) {
key = arr[i];
// if current element is positive
// do nothing
if (key > 0)
continue;
/* if current element is negative,
shift positive elements of arr[0..i-1],
to one position to their right */
j = i - 1;
while (j >= 0 && arr[j] > 0) {
arr[j + 1] = arr[j];
j = j - 1;
}
// Put negative element at its right position
arr[j + 1] = key;
}
}
// Driver program
public static void main(String[] args)
{
int arr[] = { -12, 11, -13, -5, 6, -7, 5, -3, -6 };
int n = arr.length;
RearrangePosNeg(arr, n);
printArray(arr, n);
}
}
// This code is contributed by vt_m.
Python 3
# Python 3 program to Rearrange positive # and negative numbers in a array # A utility function to print # an array of size n def printArray(arr, n): for i in range(n): print(arr[i], end=" ") print() # Function to Rearrange positive # and negative numbers in a array def RearrangePosNeg(arr, n): for i in range(1, n): key = arr[i] # if current element is positive # do nothing if (key > 0): continue ''' if current element is negative, shift positive elements of arr[0..i-1], to one position to their right ''' j = i - 1 while (j >= 0 and arr[j] > 0): arr[j + 1] = arr[j] j = j - 1 # Put negative element at its # right position arr[j + 1] = key # Driver Code if __name__ == "__main__": arr = [-12, 11, -13, -5, 6, -7, 5, -3, -6] n = len(arr) RearrangePosNeg(arr, n) printArray(arr, n) # This code is contributed # by ChitraNayal
C#
// C# program to Rearrange positive
// and negative numbers in a array
using System;
class GFG {
// A utility function to print
// an array of size n
static void printArray(int[] arr, int n)
{
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
Console.WriteLine();
}
// Function to Rearrange positive and negative
// numbers in a array
static void RearrangePosNeg(int[] arr, int n)
{
int key, j;
for (int i = 1; i < n; i++) {
key = arr[i];
// if current element is positive
// do nothing
if (key > 0)
continue;
/* if current element is negative,
shift positive elements of arr[0..i-1],
to one position to their right */
j = i - 1;
while (j >= 0 && arr[j] > 0) {
arr[j + 1] = arr[j];
j = j - 1;
}
// Put negative element at its right position
arr[j + 1] = key;
}
}
// Driver program
public static void Main()
{
int[] arr = { -12, 11, -13, -5, 6, -7, 5, -3, -6 };
int n = arr.Length;
RearrangePosNeg(arr, n);
printArray(arr, n);
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to Rearrange positive
// and negative numbers in a array
// A utility function to print
// an array of size n
function printArray($arr, $n)
{
for ($i = 0; $i < $n; $i++)
echo($arr[$i] . " ");
}
// Function to Rearrange positive and negative
// numbers in a array
function RearrangePosNeg(&$arr, $n)
{
$key; $j;
for($i = 1; $i < $n; $i++)
{
$key = $arr[$i];
// if current element is positive
// do nothing
if ($key > 0)
continue;
/* if current element is negative,
shift positive elements of arr[0..i-1],
to one position to their right */
$j = $i - 1;
while ($j >= 0 && $arr[$j] > 0)
{
$arr[$j + 1] = $arr[$j];
$j = $j - 1;
}
// Put negative element at its right position
$arr[$j + 1] = $key;
}
}
// Driver program
{
$arr = array( -12, 11, -13, -5, 6, -7, 5, -3, -6 );
$n = sizeof($arr);
RearrangePosNeg($arr, $n);
printArray($arr, $n);
}
// This code is contributed by Code_Mech.
Javascript
<script>
// Javascript program to Rearrange positive
// and negative numbers in a array
// A utility function to print
// an array of size n
function printArray(arr, n)
{
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
document.write("<br />");
}
// Function to Rearrange positive and negative
// numbers in a array
function RearrangePosNeg(arr, n)
{
let key, j;
for (let i = 1; i < n; i++) {
key = arr[i];
// if current element is positive
// do nothing
if (key > 0)
continue;
/* if current element is negative,
shift positive elements of arr[0..i-1],
to one position to their right */
j = i - 1;
while (j >= 0 && arr[j] > 0) {
arr[j + 1] = arr[j];
j = j - 1;
}
// Put negative element at its right position
arr[j + 1] = key;
}
}
// Driver Code
let arr = [ -12, 11, -13, -5, 6, -7, 5, -3, -6 ];
let n = arr.length;
RearrangePosNeg(arr, n);
printArray(arr, n);
</script>
Producción
-12 -13 -5 -7 -3 -6 11 6 5
Complejidad temporal: O(n 2 )
Espacio Auxiliar: O(1)
Hemos mantenido el orden de aparición y no hemos utilizado ninguna otra estructura de datos.
Enfoque 2: clasificación de combinación optimizada
El método de combinación del algoritmo de clasificación de combinación estándar se puede modificar para resolver este problema. Mientras fusionamos dos mitades ordenadas, digamos izquierda y derecha, debemos fusionarnos de tal manera que la parte negativa de la subarray izquierda y derecha se copie primero, seguida de la parte positiva de la subarray izquierda y derecha.
A continuación se muestra la implementación de la idea como se muestra a continuación de la siguiente manera:
C++
// C++ program to Rearrange positive and negative
// numbers in a array
#include <iostream>
using namespace std;
/* Function to print an array */
void printArray(int A[], int size)
{
for (int i = 0; i < size; i++)
cout << A[i] << " ";
cout << endl;
}
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int L[n1], R[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
// Note the order of appearance of elements should
// be maintained - we copy elements of left subarray
// first followed by that of right subarray
// copy negative elements of left subarray
while (i < n1 && L[i] < 0)
arr[k++] = L[i++];
// copy negative elements of right subarray
while (j < n2 && R[j] < 0)
arr[k++] = R[j++];
// copy positive elements of left subarray
while (i < n1)
arr[k++] = L[i++];
// copy positive elements of right subarray
while (j < n2)
arr[k++] = R[j++];
}
// Function to Rearrange positive and negative
// numbers in a array
void RearrangePosNeg(int arr[], int l, int r)
{
if (l < r) {
// Same as (l + r)/2, but avoids overflow for
// large l and h
int m = l + (r - l) / 2;
// Sort first and second halves
RearrangePosNeg(arr, l, m);
RearrangePosNeg(arr, m + 1, r);
merge(arr, l, m, r);
}
}
/* Driver program to test above functions */
int main()
{
int arr[] = { -12, 11, -13, -5, 6, -7, 5, -3, -6 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
RearrangePosNeg(arr, 0, arr_size - 1);
printArray(arr, arr_size);
return 0;
}
Java
// Java program to Rearrange positive
// and negative numbers in a array
import java.io.*;
class GFG {
/* Function to print an array */
static void printArray(int A[], int size)
{
for (int i = 0; i < size; i++)
System.out.print(A[i] + " ");
System.out.println();
}
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
static void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int L[] = new int[n1];
int R[] = new int[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
/* Merge the temp arrays back into arr[l..r]*/
// Initial index of first subarray
i = 0;
// Initial index of second subarray
j = 0;
// Initial index of merged subarray
k = l;
// Note the order of appearance of elements should
// be maintained - we copy elements of left subarray
// first followed by that of right subarray
// copy negative elements of left subarray
while (i < n1 && L[i] < 0)
arr[k++] = L[i++];
// copy negative elements of right subarray
while (j < n2 && R[j] < 0)
arr[k++] = R[j++];
// copy positive elements of left subarray
while (i < n1)
arr[k++] = L[i++];
// copy positive elements of right subarray
while (j < n2)
arr[k++] = R[j++];
}
// Function to Rearrange positive and negative
// numbers in a array
static void RearrangePosNeg(int arr[], int l, int r)
{
if (l < r) {
// Same as (l + r)/2, but avoids overflow for
// large l and h
int m = l + (r - l) / 2;
// Sort first and second halves
RearrangePosNeg(arr, l, m);
RearrangePosNeg(arr, m + 1, r);
merge(arr, l, m, r);
}
}
// Driver program
public static void main(String[] args)
{
int arr[] = { -12, 11, -13, -5, 6, -7, 5, -3, -6 };
int arr_size = arr.length;
RearrangePosNeg(arr, 0, arr_size - 1);
printArray(arr, arr_size);
}
}
// This code is contributed by vt_m.
Python3
# Python3 program to Rearrange positive # and negative numbers in a array # Function to print an array def printArray(A, size): for i in range(size): print(A[i], end=" ") print() # Merges two subarrays of arr[]. # First subarray is arr[l..m] # Second subarray is arr[m + 1..r] def merge(arr, l, m, r): i, j, k = 0, 0, 0 n1 = m - l + 1 n2 = r - m # create temp arrays */ L = [arr[l + i] for i in range(n1)] R = [arr[m + 1 + j] for j in range(n2)] # Merge the temp arrays back into arr[l..r]*/ i = 0 # Initial index of first subarray j = 0 # Initial index of second subarray k = l # Initial index of merged subarray # Note the order of appearance of elements # should be maintained - we copy elements # of left subarray first followed by that # of right subarray # copy negative elements of left subarray while (i < n1 and L[i] < 0): arr[k] = L[i] k += 1 i += 1 # copy negative elements of right subarray while (j < n2 and R[j] < 0): arr[k] = R[j] k += 1 j += 1 # copy positive elements of left subarray while (i < n1): arr[k] = L[i] k += 1 i += 1 # copy positive elements of right subarray while (j < n2): arr[k] = R[j] k += 1 j += 1 # Function to Rearrange positive and # negative numbers in a array def RearrangePosNeg(arr, l, r): if(l < r): # Same as (l + r)/2, but avoids # overflow for large l and h m = l + (r - l) // 2 # Sort first and second halves RearrangePosNeg(arr, l, m) RearrangePosNeg(arr, m + 1, r) merge(arr, l, m, r) # Driver Code arr = [-12, 11, -13, -5, 6, -7, 5, -3, -6] arr_size = len(arr) RearrangePosNeg(arr, 0, arr_size - 1) printArray(arr, arr_size) # This code is contributed by # mohit kumar 29
C#
// C# program to Rearrange positive
// and negative numbers in a array
using System;
class GFG {
/* Function to print an array */
static void printArray(int[] A, int size)
{
for (int i = 0; i < size; i++)
Console.Write(A[i] + " ");
Console.WriteLine();
}
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
static void merge(int[] arr, int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int[] L = new int[n1];
int[] R = new int[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
/* Merge the temp arrays back into arr[l..r]*/
// Initial index of first subarray
i = 0;
// Initial index of second subarray
j = 0;
// Initial index of merged subarray
k = l;
// Note the order of appearance of elements should
// be maintained - we copy elements of left subarray
// first followed by that of right subarray
// copy negative elements of left subarray
while (i < n1 && L[i] < 0)
arr[k++] = L[i++];
// copy negative elements of right subarray
while (j < n2 && R[j] < 0)
arr[k++] = R[j++];
// copy positive elements of left subarray
while (i < n1)
arr[k++] = L[i++];
// copy positive elements of right subarray
while (j < n2)
arr[k++] = R[j++];
}
// Function to Rearrange positive and negative
// numbers in a array
static void RearrangePosNeg(int[] arr, int l, int r)
{
if (l < r) {
// Same as (l + r)/2, but avoids overflow for
// large l and h
int m = l + (r - l) / 2;
// Sort first and second halves
RearrangePosNeg(arr, l, m);
RearrangePosNeg(arr, m + 1, r);
merge(arr, l, m, r);
}
}
// Driver program
public static void Main()
{
int[] arr = { -12, 11, -13, -5, 6, -7, 5, -3, -6 };
int arr_size = arr.Length;
RearrangePosNeg(arr, 0, arr_size - 1);
printArray(arr, arr_size);
}
}
// This code is contributed by vt_m.
Javascript
<script>
// javascript program to Rearrange positive and negative
// numbers in a array
/* Function to print an array */
function printArray(A , size)
{
for (i = 0; i < size; i++)
document.write(A[i] + " ");
document.write('<br>');
;
}
/* Function to reverse an array. An array can be
reversed in O(n) time and O(1) space. */
function reverse(arr , l , r)
{
if (l < r) {
arr = swap(arr, l, r);
reverse(arr, ++l, --r);
}
}
// Merges two subarrays of arr.
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
function merge(arr , l , m , r)
{
// Initial index of 1st subarray
var i = l;
// Initial index of IInd
var j = m + 1;
while (i <= m && arr[i] < 0)
i++;
// arr[i..m] is positive
while (j <= r && arr[j] < 0)
j++;
// arr[j..r] is positive
// reverse positive part of
// left sub-array (arr[i..m])
reverse(arr, i, m);
// reverse negative part of
// right sub-array (arr[m+1..j-1])
reverse(arr, m + 1, j - 1);
// reverse arr[i..j-1]
reverse(arr, i, j - 1);
}
// Function to Rearrange positive and negative
// numbers in a array
function RearrangePosNeg(arr , l , r)
{
if (l < r) {
// Same as (l+r)/2, but avoids overflow for
// large l and h
var m = l + parseInt((r - l) / 2);
// Sort first and second halves
RearrangePosNeg(arr, l, m);
RearrangePosNeg(arr, m + 1, r);
merge(arr, l, m, r);
}
}
function swap(arr , i , j)
{
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
/* Driver code*/
var arr = [ -12, 11, -13, -5, 6, -7, 5, -3, -6 ];
var arr_size = arr.length;
RearrangePosNeg(arr, 0, arr_size - 1);
printArray(arr, arr_size);
// This code contributed by shikhasingrajput
</script>
Producción
-12 -13 -5 -7 -3 -6 11 6 5
Complejidad temporal: O(n log n).
Espacio auxiliar: O (n1 + n2 + log n), log n, ya que se usa la pila implícita debido a la llamada recursiva
El problema con este enfoque es que estamos usando una array auxiliar para la fusión, pero no podemos usar ninguna estructura de datos para resolver este problema. Podemos hacer fusiones en el lugar sin usar ninguna estructura de datos. La idea está tomada de aquí .
Sean Ln y Lp la parte negativa y la parte positiva del subarreglo izquierdo respectivamente. De manera similar, Rn y Rp denotan las partes negativa y positiva del subarreglo derecho, respectivamente.
A continuación se muestran los pasos para convertir [Ln Lp Rn Rp] a [Ln Rn Lp Rp] sin usar espacio adicional.
1. Reverse Lp and Rn. We get [Lp] -> [Lp'] and [Rn] -> [Rn']
[Ln Lp Rn Rp] -> [Ln Lp’ Rn’ Rp]
2. Reverse [Lp’ Rn’]. We get [Rn Lp].
[Ln Lp’ Rn’ Rp] -> [Ln Rn Lp Rp]
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to Rearrange positive and negative
// numbers in a array
#include <bits/stdc++.h>
using namespace std;
/* Function to print an array */
void printArray(int A[], int size)
{
for (int i = 0; i < size; i++)
cout << A[i] << " ";
cout << endl;
}
/* Function to reverse an array. An array can be
reversed in O(n) time and O(1) space. */
void reverse(int arr[], int l, int r)
{
if (l < r) {
swap(arr[l], arr[r]);
reverse(arr, ++l, --r);
}
}
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int i = l; // Initial index of 1st subarray
int j = m + 1; // Initial index of IInd
while (i <= m && arr[i] < 0)
i++;
// arr[i..m] is positive
while (j <= r && arr[j] < 0)
j++;
// arr[j..r] is positive
// reverse positive part of
// left sub-array (arr[i..m])
reverse(arr, i, m);
// reverse negative part of
// right sub-array (arr[m+1..j-1])
reverse(arr, m + 1, j - 1);
// reverse arr[i..j-1]
reverse(arr, i, j - 1);
}
// Function to Rearrange positive and negative
// numbers in a array
void RearrangePosNeg(int arr[], int l, int r)
{
if (l < r) {
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l + (r - l) / 2;
// Sort first and second halves
RearrangePosNeg(arr, l, m);
RearrangePosNeg(arr, m + 1, r);
merge(arr, l, m, r);
}
}
/* Driver code */
int main()
{
int arr[] = { -12, 11, -13, -5, 6, -7, 5, -3, -6 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
RearrangePosNeg(arr, 0, arr_size - 1);
printArray(arr, arr_size);
return 0;
}
Java
// Java program to Rearrange positive and negative
// numbers in a array
class GFG {
/* Function to print an array */
static void printArray(int A[], int size)
{
for (int i = 0; i < size; i++)
System.out.print(A[i] + " ");
System.out.println("");
;
}
/* Function to reverse an array. An array can be
reversed in O(n) time and O(1) space. */
static void reverse(int arr[], int l, int r)
{
if (l < r) {
arr = swap(arr, l, r);
reverse(arr, ++l, --r);
}
}
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
static void merge(int arr[], int l, int m, int r)
{
int i = l; // Initial index of 1st subarray
int j = m + 1; // Initial index of IInd
while (i <= m && arr[i] < 0)
i++;
// arr[i..m] is positive
while (j <= r && arr[j] < 0)
j++;
// arr[j..r] is positive
// reverse positive part of
// left sub-array (arr[i..m])
reverse(arr, i, m);
// reverse negative part of
// right sub-array (arr[m+1..j-1])
reverse(arr, m + 1, j - 1);
// reverse arr[i..j-1]
reverse(arr, i, j - 1);
}
// Function to Rearrange positive and negative
// numbers in a array
static void RearrangePosNeg(int arr[], int l, int r)
{
if (l < r) {
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l + (r - l) / 2;
// Sort first and second halves
RearrangePosNeg(arr, l, m);
RearrangePosNeg(arr, m + 1, r);
merge(arr, l, m, r);
}
}
static int[] swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
/* Driver code*/
public static void main(String[] args)
{
int arr[] = { -12, 11, -13, -5, 6, -7, 5, -3, -6 };
int arr_size = arr.length;
RearrangePosNeg(arr, 0, arr_size - 1);
printArray(arr, arr_size);
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python3 program to Rearrange positive # and negative numbers in an array # Function to print an array def printArray(A, size): for i in range(0, size): print(A[i], end=" ") print() # Function to reverse an array. An array can # be reversed in O(n) time and O(1) space. def reverse(arr, l, r): if l < r: arr[l], arr[r] = arr[r], arr[l] l, r = l + 1, r - 1 reverse(arr, l, r) # Merges two subarrays of arr[]. # First subarray is arr[l..m] # Second subarray is arr[m + 1..r] def merge(arr, l, m, r): i = l # Initial index of 1st subarray j = m + 1 # Initial index of IInd while i <= m and arr[i] < 0: i += 1 # arr[i..m] is positive while j <= r and arr[j] < 0: j += 1 # arr[j..r] is positive # reverse positive part of left # sub-array (arr[i..m]) reverse(arr, i, m) # reverse negative part of right # sub-array (arr[m + 1..j-1]) reverse(arr, m + 1, j - 1) # reverse arr[i..j-1] reverse(arr, i, j - 1) # Function to Rearrange positive # and negative numbers in a array def RearrangePosNeg(arr, l, r): if l < r: # Same as (l + r)/2, but avoids # overflow for large l and h m = l + (r - l) // 2 # Sort first and second halves RearrangePosNeg(arr, l, m) RearrangePosNeg(arr, m + 1, r) merge(arr, l, m, r) # Driver Code if __name__ == "__main__": arr = [-12, 11, -13, -5, 6, -7, 5, -3, -6] arr_size = len(arr) RearrangePosNeg(arr, 0, arr_size - 1) printArray(arr, arr_size) # This code is contributed by Rituraj Jain
C#
// C# program to Rearrange positive and negative
// numbers in a array
using System;
class GFG {
/* Function to print an array */
static void printArray(int[] A, int size)
{
for (int i = 0; i < size; i++)
Console.Write(A[i] + " ");
Console.WriteLine("");
;
}
/* Function to reverse an array. An array can be
reversed in O(n) time and O(1) space. */
static void reverse(int[] arr, int l, int r)
{
if (l < r) {
arr = swap(arr, l, r);
reverse(arr, ++l, --r);
}
}
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
static void merge(int[] arr, int l, int m, int r)
{
int i = l; // Initial index of 1st subarray
int j = m + 1; // Initial index of IInd
while (i <= m && arr[i] < 0)
i++;
// arr[i..m] is positive
while (j <= r && arr[j] < 0)
j++;
// arr[j..r] is positive
// reverse positive part of
// left sub-array (arr[i..m])
reverse(arr, i, m);
// reverse negative part of
// right sub-array (arr[m+1..j-1])
reverse(arr, m + 1, j - 1);
// reverse arr[i..j-1]
reverse(arr, i, j - 1);
}
// Function to Rearrange positive and negative
// numbers in a array
static void RearrangePosNeg(int[] arr, int l, int r)
{
if (l < r) {
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l + (r - l) / 2;
// Sort first and second halves
RearrangePosNeg(arr, l, m);
RearrangePosNeg(arr, m + 1, r);
merge(arr, l, m, r);
}
}
static int[] swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
/* Driver code*/
public static void Main()
{
int[] arr = { -12, 11, -13, -5, 6, -7, 5, -3, -6 };
int arr_size = arr.Length;
RearrangePosNeg(arr, 0, arr_size - 1);
printArray(arr, arr_size);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript program to Rearrange positive and negative
// numbers in a array
/* Function to print an array */
function printArray(A,size)
{
for (let i = 0; i < size; i++)
document.write(A[i] + " ");
document.write("<br>");
}
/* Function to reverse an array. An array can be
reversed in O(n) time and O(1) space. */
function reverse(arr,l,r)
{
if (l < r) {
arr = swap(arr, l, r);
reverse(arr, ++l, --r);
}
}
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
function merge(arr,l,m,r)
{
let i = l; // Initial index of 1st subarray
let j = m + 1; // Initial index of IInd
while (i <= m && arr[i] < 0)
i++;
// arr[i..m] is positive
while (j <= r && arr[j] < 0)
j++;
// arr[j..r] is positive
// reverse positive part of
// left sub-array (arr[i..m])
reverse(arr, i, m);
// reverse negative part of
// right sub-array (arr[m+1..j-1])
reverse(arr, m + 1, j - 1);
// reverse arr[i..j-1]
reverse(arr, i, j - 1);
}
// Function to Rearrange positive and negative
// numbers in a array
function RearrangePosNeg(arr,l,r)
{
if (l < r) {
// Same as (l+r)/2, but avoids overflow for
// large l and h
let m = l + Math.floor((r - l) / 2);
// Sort first and second halves
RearrangePosNeg(arr, l, m);
RearrangePosNeg(arr, m + 1, r);
merge(arr, l, m, r);
}
}
function swap(arr,i,j)
{
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
/* Driver code*/
let arr=[-12, 11, -13, -5, 6, -7, 5, -3, -6 ];
let arr_size = arr.length;
RearrangePosNeg(arr, 0, arr_size - 1);
printArray(arr, arr_size);
// This code is contributed by unknown2108
</script>
Producción
-12 -13 -5 -7 -3 -6 11 6 5
Complejidad de tiempo: O(n log n), O(Log n) espacio para llamadas recursivas y sin estructura de datos adicional.
Espacio auxiliar: O (log n), ya que se usa la pila implícita debido a la llamada recursiva
Enfoque 4: Uso de partición_estable
C++
#include <bits/stdc++.h>
using namespace std;
void Rearrange(int arr[], int n)
{
stable_partition(arr,arr+n,[](int x){return x<0;});
}
int main()
{
int n=4;
int arr[n]={-3, 3, -2, 2};
Rearrange( arr, n);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
Producción
-3 -2 3 2
Complejidad temporal: O(n 2 )
Espacio Auxiliar: O(n)
Enfoque 5: Uso de la ventana deslizante con la técnica de dos punteros
Esta técnica utiliza una ventana deslizante de números positivos para cambiar los números negativos al comienzo de la ventana, mientras avanza.
C++
#include <iostream>
using namespace std;
void rearrangePosNegWithOrder(int *arr, int size)
{
int i = 0, j = 0;
while (j < size) {
if (arr[j] >= 0) {
j++;
}
else {
for (int k = j; k > i; k--) {
int temp = arr[k];
arr[k] = arr[k - 1];
arr[k - 1] = temp;
}
i++;
j++;
}
}
}
int main()
{
int arr[] = { -12, 11, -13, -5, 6, -7, 5, -3, -6 };
int size = *(&arr + 1) - arr;
rearrangePosNegWithOrder(arr, size);
for (int i : arr) {
cout << i;
cout << " ";
}
return 0;
}
Java
import java.io.*;
class GFG {
// Here the size of window increases as it encounters
// positive numbers
public static void rearrangePosNegWithOrder(int[] arr)
{
int i = 0, j = 0;
while (j < arr.length) {
if (arr[j] >= 0) {
j++;
}
else {
for (int k = j; k > i; k--) {
int temp = arr[k];
arr[k] = arr[k - 1];
arr[k - 1] = temp;
}
i++;
j++;
}
}
}
public static void main(String[] args)
{
int arr[] = { -12, 11, -13, -5, 6, -7, 5, -3, -6 };
rearrangePosNegWithOrder(arr);
for (int i : arr) {
System.out.print(i + " ");
}
}
}
Producción
-12 -13 -5 -7 -3 -6 11 6 5
Complejidad de tiempo : O (n * ventana)
Espacio Auxiliar : O(1)
Este artículo es una contribución de Aditya Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA