Dado un arr[ ] de tamaño N , que contiene enteros positivos, negativos y un cero. La tarea es reorganizar la array de tal manera que todos los números negativos estén a la izquierda del 0 y todos los números positivos estén a la derecha.
Nota: No es obligatorio mantener el orden de los números. Si hay múltiples respuestas posibles, imprima cualquiera de ellas.
Ejemplos:
Entrada: arr[] = {1, 0, -2, 3, 4, -5, -7, 9, -3}
Salida: -2 -3 -5 -7 0 1 9 3 4
Explicación: Los números negativos son -2, -5, -7 y -3.Entrada: arr[] = {-10, 5, -2, 0, -4, 5, 17, -9, -13, 11}
Salida: -10 -2 -4 -13 -9 0 17 5 5 11
Enfoque ingenuo: cree una array de tamaño N y empuje números negativos desde el principio y números positivos desde el final. Además, llene el único lugar restante con 0.
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Enfoque eficiente: la idea es encontrar el índice donde se almacena 0 en la array. Una vez que se encuentra el 0, considere ese índice como un pivote. Mueva todos los valores negativos al lado izquierdo del pivote y así los valores del lado derecho serán positivos automáticamente.
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;
// Function to rearrange the array,
// such that all the negative appear
// on the left side of 0 and all
// positive appear on the right side of 0
void rearrangeArray(int arr[], int N)
{
int i, ind;
// Find index of 0
for (i = 0; i < N; i++) {
if (arr[i] == 0) {
ind = i;
break;
}
}
// Pivot the 0 element.
int j = -1, k, temp;
for (k = 0; k < N; k++) {
if (arr[k] < 0) {
j += 1;
// Don't swap with pivot.
if (arr[j] == 0)
j += 1;
swap(arr[j], arr[k]);
}
}
// swap the pivot with last negative.
swap(arr[ind], arr[j]);
for (int i = 0; i < N; i++) {
cout << arr[i] << " ";
}
}
// Driver Code
int main()
{
int arr[] = { 1, 0, -2, 3, 4, -5,
-7, 9, -3 };
int N = sizeof(arr) / sizeof(int);
rearrangeArray(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Function to rearrange the array,
// such that all the negative appear
// on the left side of 0 and all
// positive appear on the right side of 0
static void rearrangeArray(int arr[], int N)
{
int i, ind = -1;
// Find index of 0
for (i = 0; i < N; i++) {
if (arr[i] == 0) {
ind = i;
break;
}
}
// Pivot the 0 element.
int j = -1, k, temp;
for (k = 0; k < N; k++) {
if (arr[k] < 0) {
j += 1;
// Don't swap with pivot.
if (arr[j] == 0)
j += 1;
//swap
temp = arr[j];
arr[j] = arr[k];
arr[k] = temp;
}
}
// swap the pivot with last negative.
int temp2 = arr[j];
arr[j] = arr[ind];
arr[ind] = temp2;
for (j = 0; j < N; j++) {
System.out.print(arr[j] + " ");
}
}
// Driver Code
public static void main (String[] args) {
int arr[] = { 1, 0, -2, 3, 4, -5,
-7, 9, -3 };
int N = arr.length;
rearrangeArray(arr, N);
}
}
// This code is contributed by hrithikgarg03188
Python3
# Python code for the above approach # Function to rearrange the array, # such that all the negative appear # on the left side of 0 and all # positive appear on the right side of 0 def rearrangeArray(arr, N): ind = None # Find index of 0 for i in range(N): if (arr[i] == 0): ind = i; break; # Pivot the 0 element. j = -1 temp = None for k in range(N): if (arr[k] < 0): j += 1; # Don't swap with pivot. if (arr[j] == 0): j += 1; temp = arr[j]; arr[j] = arr[k]; arr[k] = temp; # swap the pivot with last negative. temp = arr[ind]; arr[ind] = arr[j]; arr[j] = temp; for i in range(N): print(arr[i], end=" "); # Driver Code arr = [1, 0, -2, 3, 4, -5, -7, 9, -3]; N = len(arr) rearrangeArray(arr, N); # This code is contributed by Saurabh Jaiswal
C#
// C# program for the above approach
using System;
class GFG
{
// Function to rearrange the array,
// such that all the negative appear
// on the left side of 0 and all
// positive appear on the right side of 0
static void rearrangeArray(int[] arr, int N)
{
int i, ind = -1;
// Find index of 0
for (i = 0; i < N; i++)
{
if (arr[i] == 0)
{
ind = i;
break;
}
}
// Pivot the 0 element.
int j = -1, k, temp;
for (k = 0; k < N; k++)
{
if (arr[k] < 0)
{
j += 1;
// Don't swap with pivot.
if (arr[j] == 0)
j += 1;
//swap
temp = arr[j];
arr[j] = arr[k];
arr[k] = temp;
}
}
// swap the pivot with last negative.
int temp2 = arr[j];
arr[j] = arr[ind];
arr[ind] = temp2;
for (j = 0; j < N; j++)
{
Console.Write(arr[j] + " ");
}
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 0, -2, 3, 4, -5, -7, 9, -3 };
int N = arr.Length;
rearrangeArray(arr, N);
}
}
// This code is contributed by gfgking
Javascript
<script>
// JavaScript code for the above approach
// Function to rearrange the array,
// such that all the negative appear
// on the left side of 0 and all
// positive appear on the right side of 0
function rearrangeArray(arr, N) {
let i, ind;
// Find index of 0
for (i = 0; i < N; i++) {
if (arr[i] == 0) {
ind = i;
break;
}
}
// Pivot the 0 element.
let j = -1, k, temp;
for (k = 0; k < N; k++) {
if (arr[k] < 0) {
j += 1;
// Don't swap with pivot.
if (arr[j] == 0)
j += 1;
let temp = arr[j];
arr[j] = arr[k];
arr[k] = temp;
}
}
// swap the pivot with last negative.
temp = arr[ind];
arr[ind] = arr[j];
arr[j] = temp;
for (let i = 0; i < N; i++) {
document.write(arr[i] + " ");
}
}
// Driver Code
let arr = [1, 0, -2, 3, 4, -5,
-7, 9, -3];
let N = arr.length;
rearrangeArray(arr, N);
// This code is contributed by Potta Lokesh
</script>
-2 -3 -5 -7 0 1 3 9 4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por pintusaini y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA