Una array contiene números positivos y negativos en orden aleatorio. Reorganice los elementos de la array para que todos los números negativos aparezcan antes que todos los números positivos.
Ejemplos:
Entrada: -12, 11, -13, -5, 6, -7, 5, -3, -6
Salida: -12 -13 -5 -7 -3 -6 11 6 5
Nota: El orden de los elementos no es importante aquí.
Enfoque ingenuo: la idea es ordenar la array de elementos, esto asegurará que todos los elementos negativos vendrán antes que todos los elementos positivos.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
void move(vector<int>& arr){
sort(arr.begin(),arr.end());
}
int main() {
vector<int> arr = { -1, 2, -3, 4, 5, 6, -7, 8, 9 };
move(arr);
for (int e : arr)
cout<<e << " ";
return 0;
}
// This code is contributed by repakaeshwaripriya
Java
// Java program to move all negative numbers to the
// beginning and all positive numbers to the end with
// constant extra space
import java.util.*;
public class Gfg {
public static void move(int[] arr)
{
Arrays.sort(arr);
}
// Driver code
public static void main(String[] args)
{
int[] arr = { -1, 2, -3, 4, 5, 6, -7, 8, 9 };
move(arr);
for (int e : arr)
System.out.print(e + " ");
}
}
// This article is contributed by aadityapburujwale
Python3
# Python code for the same approach def move(arr): arr.sort() # driver code arr = [ -1, 2, -3, 4, 5, 6, -7, 8, 9 ] move(arr) for e in arr: print(e , end = " ") # This code is contributed by shinjanpatra
C#
// C# program to move all negative numbers to the
// beginning and all positive numbers to the end with
// constant extra space
using System;
using System.Collections;
public class Gfg {
public static void move(int[] arr)
{
Array.Sort(arr);
}
// Driver code
public static void Main()
{
int[] arr = { -1, 2, -3, 4, 5, 6, -7, 8, 9 };
move(arr);
foreach (int e in arr)
Console.Write(e + " ");
}
}
// This code is contributed by Saurabh Jaiswal
Javascript
<script>
// JavaScript Code for the same approach
function move(arr){
arr.sort();
}
// driver code
let arr = [ -1, 2, -3, 4, 5, 6, -7, 8, 9 ];
move(arr);
for (let e of arr)
document.write(e , " ");
// This code is contributed by shinjanpatra
</script>
Producción
-7 -3 -1 2 4 5 6 8 9
Complejidad de tiempo: O(n*log(n)), donde n es la longitud de la array dada.
Espacio Auxiliar: O(n)
Enfoque Eficiente 1:
La idea es simplemente aplicar el proceso de partición de clasificación rápida .
C++
// A C++ program to put all negative
// numbers before positive numbers
#include <bits/stdc++.h>
using namespace std;
void rearrange(int arr[], int n)
{
int j = 0;
for (int i = 0; i < n; i++) {
if (arr[i] < 0) {
if (i != j)
swap(arr[i], arr[j]);
j++;
}
}
}
// A utility function to print an array
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
}
// Driver code
int main()
{
int arr[] = { -1, 2, -3, 4, 5, 6, -7, 8, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
rearrange(arr, n);
printArray(arr, n);
return 0;
}
Java
// Java program to put all negative
// numbers before positive numbers
import java.io.*;
class GFG {
static void rearrange(int arr[], int n)
{
int j = 0, temp;
for (int i = 0; i < n; i++) {
if (arr[i] < 0) {
if (i != j) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
j++;
}
}
}
// A utility function to print an array
static void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
// Driver code
public static void main(String args[])
{
int arr[] = { -1, 2, -3, 4, 5, 6, -7, 8, 9 };
int n = arr.length;
rearrange(arr, n);
printArray(arr, n);
}
}
// This code is contributed by Nikita Tiwari.
Python3
# A Python 3 program to put # all negative numbers before # positive numbers def rearrange(arr, n ) : # Please refer partition() in # below post # https://www.geeksforgeeks.org / quick-sort / j = 0 j = 0 for i in range(0, n) : if (arr[i] < 0) : temp = arr[i] arr[i] = arr[j] arr[j]= temp j = j + 1 print(arr) # Driver code arr = [-1, 2, -3, 4, 5, 6, -7, 8, 9] n = len(arr) rearrange(arr, n) # This code is contributed by Nikita Tiwari.
C#
// C# program to put all negative
// numbers before positive numbers
using System;
class GFG {
static void rearrange(int[] arr, int n)
{
int j = 0, temp;
for (int i = 0; i < n; i++) {
if (arr[i] < 0) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
j++;
}
}
}
// A utility function to print an array
static void printArray(int[] arr, int n)
{
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
// Driver code
public static void Main()
{
int[] arr = { -1, 2, -3, 4, 5, 6, -7, 8, 9 };
int n = arr.Length;
rearrange(arr, n);
printArray(arr, n);
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// A PHP program to put all negative
// numbers before positive numbers
function rearrange(&$arr, $n)
{
$j = 0;
for ($i = 0; $i < $n; $i++)
{
if ($arr[$i] < 0)
{
if ($i != $j)
{
$temp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $temp;
}
$j++;
}
}
}
// A utility function to print an array
function printArray(&$arr, $n)
{
for ($i = 0; $i < $n; $i++)
echo $arr[$i]." ";
}
// Driver code
$arr = array(-1, 2, -3, 4, 5, 6, -7, 8, 9 );
$n = sizeof($arr);
rearrange($arr, $n);
printArray($arr, $n);
// This code is contributed by ChitraNayal
?>
Javascript
<script>
// A JavaScript program to put all negative
// numbers before positive numbers
function rearrange(arr, n)
{
let j = 0;
for (let i = 0; i < n; i++) {
if (arr[i] < 0) {
if (i != j){
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
j++;
}
}
}
// A utility function to print an array
function printArray(arr, n)
{
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
}
// Driver code
let arr = [ -1, 2, -3, 4, 5, 6, -7, 8, 9 ];
let n = arr.length;
rearrange(arr, n);
printArray(arr, n);
// This code is contributed by Surbhi Tyagi.
</script>
Producción
-1 -3 -7 4 5 6 2 8 9
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque de dos punteros: la idea es resolver este problema con espacio constante y tiempo lineal mediante el uso de un enfoque de dos punteros o dos variables en el que simplemente tomamos dos variables como izquierda y derecha que contienen los índices 0 y N-1. Solo falta comprobar que:
- Compruebe si los elementos del puntero izquierdo y derecho son negativos, simplemente incremente el puntero izquierdo.
- De lo contrario, si el elemento de la izquierda es positivo y el elemento de la derecha es negativo, simplemente intercambie los elementos e incremente y disminuya simultáneamente los punteros izquierdo y derecho.
- De lo contrario, si el elemento izquierdo es positivo y el elemento derecho también es positivo, simplemente disminuya el puntero derecho.
- Repita los 3 pasos anteriores hasta que el puntero izquierdo ≤ puntero derecho.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above
// approach
#include <iostream>
using namespace std;
// Function to shift all the
// negative elements on left side
void shiftall(int arr[], int left,
int right)
{
// Loop to iterate over the
// array from left to the right
while (left<=right)
{
// Condition to check if the left
// and the right elements are
// negative
if (arr[left] < 0 && arr[right] < 0)
left+=1;
// Condition to check if the left
// pointer element is positive and
// the right pointer element is negative
else if (arr[left]>0 && arr[right]<0)
{
int temp=arr[left];
arr[left]=arr[right];
arr[right]=temp;
left+=1;
right-=1;
}
// Condition to check if both the
// elements are positive
else if (arr[left]>0 && arr[right] >0)
right-=1;
else{
left += 1;
right -= 1;
}
}
}
// Function to print the array
void display(int arr[], int right){
// Loop to iterate over the element
// of the given array
for (int i=0;i<=right;++i){
cout<<arr[i]<<" ";
}
cout<<endl;
}
// Driver Code
int main()
{
int arr[] = {-12, 11, -13, -5,
6, -7, 5, -3, 11};
int arr_size = sizeof(arr) /
sizeof(arr[0]);
// Function Call
shiftall(arr,0,arr_size-1);
display(arr,arr_size-1);
return 0;
}
//added by Dhruv Goyal
Java
// Java program of the above
// approach
import java.io.*;
class GFG{
// Function to shift all the
// negative elements on left side
static void shiftall(int[] arr, int left,
int right)
{
// Loop to iterate over the
// array from left to the right
while (left <= right)
{
// Condition to check if the left
// and the right elements are
// negative
if (arr[left] < 0 && arr[right] < 0)
left++;
// Condition to check if the left
// pointer element is positive and
// the right pointer element is negative
else if (arr[left] > 0 && arr[right] < 0)
{
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
// Condition to check if both the
// elements are positive
else if (arr[left] > 0 && arr[right] > 0)
right--;
else
{
left++;
right--;
}
}
}
// Function to print the array
static void display(int[] arr, int right)
{
// Loop to iterate over the element
// of the given array
for(int i = 0; i <= right; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Drive code
public static void main(String[] args)
{
int[] arr = { -12, 11, -13, -5,
6, -7, 5, -3, 11 };
int arr_size = arr.length;
// Function Call
shiftall(arr, 0, arr_size - 1);
display(arr, arr_size - 1);
}
}
// This code is contributed by dhruvgoyal267
Python3
# Python3 program of the # above approach # Function to shift all the # the negative elements to # the left of the array def shiftall(arr,left,right): # Loop to iterate while the # left pointer is less than # the right pointer while left<=right: # Condition to check if the left # and right pointer negative if arr[left] < 0 and arr[right] < 0: left+=1 # Condition to check if the left # pointer element is positive and # the right pointer element is # negative else if arr[left]>0 and arr[right]<0: arr[left], arr[right] = \ arr[right],arr[left] left+=1 right-=1 # Condition to check if the left # pointer is positive and right # pointer as well else if arr[left]>0 and arr[right]>0: right-=1 else: left+=1 right-=1 # Function to print the array def display(arr): for i in range(len(arr)): print(arr[i], end=" ") print() # Driver Code if __name__ == "__main__": arr=[-12, 11, -13, -5, \ 6, -7, 5, -3, 11] n=len(arr) shiftall(arr,0,n-1) display(arr) # Sumit Singh
C#
// C# program of the above
// approach
using System.IO;
using System;
class GFG
{
// Function to shift all the
// negative elements on left side
static void shiftall(int[] arr, int left,int right)
{
// Loop to iterate over the
// array from left to the right
while (left <= right)
{
// Condition to check if the left
// and the right elements are
// negative
if (arr[left] < 0 && arr[right] < 0)
left++;
// Condition to check if the left
// pointer element is positive and
// the right pointer element is negative
else if (arr[left] > 0 && arr[right] < 0)
{
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
// Condition to check if both the
// elements are positive
else if (arr[left] > 0 && arr[right] > 0)
right--;
else
{
left++;
right--;
}
}
}
// Function to print the array
static void display(int[] arr, int right)
{
// Loop to iterate over the element
// of the given array
for(int i = 0; i <= right; ++i)
{
Console.Write(arr[i] + " ");
}
Console.WriteLine();
}
// Drive code
static void Main()
{
int[] arr = {-12, 11, -13, -5, 6, -7, 5, -3, 11};
int arr_size = arr.Length;
shiftall(arr, 0, arr_size - 1);
display(arr, arr_size - 1);
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// Javascript program of the above
// approach
// Function to shift all the
// negative elements on left side
function shiftall(arr, left, right)
{
// Loop to iterate over the
// array from left to the right
while (left <= right)
{
// Condition to check if the left
// and the right elements are
// negative
if (arr[left] < 0 && arr[right] < 0)
left += 1;
// Condition to check if the left
// pointer element is positive and
// the right pointer element is negative
else if(arr[left] > 0 && arr[right] < 0)
{
let temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left += 1;
right -= 1;
}
// Condition to check if both the
// elements are positive
else if (arr[left] > 0 && arr[right] > 0)
right -= 1;
else
{
left += 1;
right -= 1;
}
}
}
// Function to print the array
function display(arr, right)
{
// Loop to iterate over the element
// of the given array
for(let i = 0; i < right; i++)
document.write(arr[i] + " ");
}
// Driver Code
let arr = [ -12, 11, -13, -5,
6, -7, 5, -3, 11 ];
let arr_size = arr.length;
// Function Call
shiftall(arr, 0, arr_size - 1);
display(arr, arr_size);
// This code is contributed by annianni
</script>
Producción
-12 -3 -13 -5 -7 6 5 11 11
Este es un algoritmo de reorganización en el lugar para organizar los números positivos y negativos donde no se mantiene el orden de los elementos.
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
El problema se vuelve difícil si necesitamos mantener el orden de los elementos. Consulte Reorganizar números positivos y negativos con espacio adicional constante para obtener más detalles.
Este artículo es una contribución de Apoorva . 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 GeeksforGeek y ayude a otros Geeks.
Enfoque 3:
Aquí, usaremos el famoso algoritmo de la bandera nacional holandesa para dos «colores». El primer color será para todos los enteros negativos y el segundo color será para todos los enteros positivos. Dividiremos la array en tres particiones con la ayuda de dos punteros, bajo y alto.
- ar[1…low-1] enteros negativos
- ar[bajo…alto] desconocido
- ar[alto+1…N] enteros positivos
Ahora, exploramos la array con la ayuda del puntero bajo, reduciendo la partición desconocida y moviendo elementos a su partición correcta en el proceso. Hacemos esto hasta que hayamos explorado todos los elementos y el tamaño de la partición desconocida se reduzca a cero.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <iostream>
using namespace std;
// Swap Function.
void swap(int &a,int &b){
int temp =a;
a=b;
b=temp;
}
// Using Dutch National Flag Algorithm.
void reArrange(int arr[],int n){
int low =0,high = n-1;
while(low<high){
if(arr[low]<0){
low++;
}else if(arr[high]>0){
high--;
}else{
swap(arr[low],arr[high]);
}
}
}
void displayArray(int arr[],int n){
for(int i=0;i<n;i++){
cout<<arr[i]<<" ";
}
cout<<endl;
}
int main() {
// Data
int arr[] = {1, 2, -4, -5, 2, -7, 3, 2, -6, -8, -9, 3, 2, 1};
int n = sizeof(arr)/sizeof(arr[0]);
reArrange(arr,n);
displayArray(arr,n);
return 0;
}
Java
// Java program to move all negative numbers to the
// beginning and all positive numbers to the end with
// constant extra space
public class Gfg {
// a utility function to swap two elements of an array
public static void swap(int[] ar, int i, int j)
{
int t = ar[i];
ar[i] = ar[j];
ar[j] = t;
}
// function to shilf all negative integers to the left
// and all positive integers to the right
// using Dutch National Flag Algorithm
public static void move(int[] ar)
{
int low = 0;
int high = ar.length - 1;
while (low <= high) {
if (ar[low] <= 0)
low++;
else
swap(ar, low, high--);
}
}
// Driver code
public static void main(String[] args)
{
int[] ar = { 1, 2, -4, -5, 2, -7, 3,
2, -6, -8, -9, 3, 2, 1 };
move(ar);
for (int e : ar)
System.out.print(e + " ");
}
}
// This code is contributed by Vedant Harshit
Python3
# Python code for the approach
# Using Dutch National Flag Algorithm.
def reArrange(arr, n):
low,high = 0, n - 1
while(low<high):
if(arr[low] < 0):
low += 1
elif(arr[high] > 0):
high -= 1
else:
arr[low],arr[high] = arr[high],arr[low]
def displayArray(arr, n):
for i in range(n):
print(arr[i],end = " ")
print('')
# driver code
# Data
arr = [1, 2, -4, -5, 2, -7, 3, 2, -6, -8, -9, 3, 2, 1]
n = len(arr)
reArrange(arr,n)
displayArray(arr,n)
# This code is contributed by shinjanpatra
C#
// Include namespace system
using System;
// C# program to move all negative numbers to the
// beginning and all positive numbers to the end with
// constant extra space
public class Gfg
{
// a utility function to swap two elements of an array
public static void swap(int[] ar, int i, int j)
{
var t = ar[i];
ar[i] = ar[j];
ar[j] = t;
}
// function to shilf all negative integers to the left
// and all positive integers to the right
// using Dutch National Flag Algorithm
public static void move(int[] ar)
{
var low = 0;
var high = ar.Length - 1;
while (low <= high)
{
if (ar[low] <= 0)
{
low++;
}
else
{
Gfg.swap(ar, low, high--);
}
}
}
// Driver code
public static void Main(String[] args)
{
int[] ar = {1, 2, -4, -5, 2, -7, 3, 2, -6, -8, -9, 3, 2, 1};
Gfg.move(ar);
foreach (int e in ar)
{ Console.Write(e.ToString() + " ");
}
}
}
// This code is contributed by mukulsomukesh
Javascript
<script>
// JavaScript code for the approach
// Using Dutch National Flag Algorithm.
function reArrange(arr, n){
let low = 0,high = n - 1
while(low<high){
if(arr[low] < 0)
low += 1
else if(arr[high] > 0)
high -= 1
else{
let temp = arr[low]
arr[low] = arr[high]
arr[high] = temp
}
}
}
function displayArray(arr, n){
for(let i = 0; i < n; i++){
document.write(arr[i]," ")
}
document.write('</br>')
}
// driver code
// Data
let arr = [1, 2, -4, -5, 2, -7, 3, 2, -6, -8, -9, 3, 2, 1]
let n = arr.length
reArrange(arr,n)
displayArray(arr,n)
// This code is contributed by shinjanpatra
</script>
Producción
-9 -8 -4 -5 -6 -7 3 2 2 2 1 3 2 1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Aquí no importa el orden de los elementos. Explicación y código aportados por Vedant Harshit
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