Dada una array y un rango [ lowVal , highVal ], divida la array alrededor del rango de modo que la array se divida en tres partes.
- Todos los elementos más pequeños que lowVal vienen primero.
- Todos los elementos en el rango lowVal a highVal vienen a continuación.
- Todos los elementos mayores que highVVal aparecen al final.
- El orden relativo de los números no debe cambiarse.
Ejemplos:
Entrada: arr[] = {1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32}, lowVal = 14, highVal = 20
Salida: arr[] = { 1 5 4 2 3 1 14 20 20 54 87 98 32 }Entrada: arr[] = {1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32}, lowVal = 20, highVal = 20
Salida: arr[] = { 1 14 5 4 2 3 1 20 20 54 87 98 32 }
Enfoque: este enfoque se basa en el uso de estructuras de datos adicionales para almacenar los elementos menores que lowVal, entre lowVal y highVal, y elementos mayores que highVal. Usaremos 3 colas para mantener el orden original de los elementos.
- Atraviesa la array uno por uno
- Inserte los elementos de la array en la cola respectiva uno por uno
- Al final,
- Saque todos los elementos en la cola 1 con elementos menores que lowVal
- Luego saca todos los elementos en la cola 2 con elementos entre lowVal y highVal
- Luego saque todos los elementos en la cola 3 con elementos mayores que highVal.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement three way
// partitioning of an array without
// changing the relative ordering
#include <bits/stdc++.h>
using namespace std;
// Function to do three way partitioning
vector<int> pivotArray(vector<int>& nums, int lowVal,
int highVal)
{
// Declaring 3 queues
queue<int> before, same, after;
// Traverse the array elements one by one
for (int i = 0; i < nums.size(); i++) {
// If the element is
// less than pivot range
// insert it into queue before
if (nums[i] < lowVal)
before.push(nums[i]);
// Else If the element is
// in between pivot range
// insert it into queue same
else if (nums[i] > highVal)
after.push(nums[i]);
// Else If the element is
// less than pivot range
// insert it into queue after
else
same.push(nums[i]);
}
int k = 0;
// Now insert all elements
// in queue before and
// insert into final vector
while (before.size() > 0) {
nums[k++] = before.front();
before.pop();
}
// Now insert all elements
// in queue same and
// insert into final vector
while (same.size() > 0) {
nums[k++] = same.front();
same.pop();
}
// Now insert all elements
// in queue after and
// insert into final vector
while (after.size() > 0) {
nums[k++] = after.front();
after.pop();
}
// Return the final vector
return nums;
}
// Driver code
int main()
{
vector<int> arr
= { 1, 14, 5, 20, 4, 2, 54,
20, 87, 98, 3, 1, 32 };
int lowVal = 20, highVal = 20;
pivotArray(arr, lowVal, highVal);
for (int i = 0; i < arr.size(); i++) {
cout << arr[i] << " ";
}
return 0;
}
Java
// JAVA code to implement three way
// partitioning of an array without
// changing the relative ordering
import java.util.*;
class GFG {
// Function to do three way partitioning
public static int[] pivotArray(int[] nums, int lowVal,
int highVal)
{
// Declaring 3 queues
Queue<Integer> before = new LinkedList<>();
Queue<Integer> same = new LinkedList<>();
Queue<Integer> after = new LinkedList<>();
// Traverse the array elements one by one
for (int i = 0; i < nums.length; i++) {
// If the element is
// less than pivot range
// insert it into queue before
if (nums[i] < lowVal)
before.add(nums[i]);
// Else If the element is
// in between pivot range
// insert it into queue same
else if (nums[i] > highVal)
after.add(nums[i]);
// Else If the element is
// less than pivot range
// insert it into queue after
else
same.add(nums[i]);
}
int k = 0;
// Now insert all elements
// in queue before and
// insert into final vector
while (before.size() > 0) {
nums[k++] = before.poll();
}
// Now insert all elements
// in queue same and
// insert into final vector
while (same.size() > 0) {
nums[k++] = same.poll();
}
// Now insert all elements
// in queue after and
// insert into final vector
while (after.size() > 0) {
nums[k++] = after.poll();
}
// Return the final vector
return nums;
}
// Driver code
public static void main(String[] args)
{
int arr[] = new int[] { 1, 14, 5, 20, 4, 2, 54,
20, 87, 98, 3, 1, 32 };
int lowVal = 20, highVal = 20;
pivotArray(arr, lowVal, highVal);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
// This code is contributed by Taranpreet
Python3
# Python 3 code to implement three way # partitioning of an array without # changing the relative ordering # Function to do three way partitioning def pivotArray(nums, lowVal, highVal): # Declaring 3 queues before = [] same = [] after = [] # Traverse the array elements one by one for i in range(len(nums)): # If the element is # less than pivot range # insert it into queue before if (nums[i] < lowVal): before.append(nums[i]) # Else If the element is # in between pivot range # insert it into queue same elif (nums[i] > highVal): after.append(nums[i]) # Else If the element is # less than pivot range # insert it into queue after else: same.append(nums[i]) k = 0 # Now insert all elements # in queue before and # insert into final vector while (len(before) > 0): nums[k] = before[0] k += 1 before.pop(0) # Now insert all elements # in queue same and # insert into final vector while (len(same) > 0): nums[k] = same[0] same.pop(0) k += 1 # Now insert all elements # in queue after and # insert into final vector while (len(after) > 0): nums[k] = after[0] k += 1 after.pop(0) # Return the final vector return nums # Driver code if __name__ == "__main__": arr = [1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32] lowVal = 20 highVal = 20 pivotArray(arr, lowVal, highVal) for i in range(len(arr)): print(arr[i], end=" ") # This code is contributed by ukasp.
C#
// C# code to implement three way
using System;
using System.Collections;
public class GFG{
// partitioning of an array without
// changing the relative ordering
// Function to do three way partitioning
static int[] pivotArray(int[] nums, int lowVal,
int highVal)
{
// Declaring 3 queues
Queue before = new Queue();
Queue same = new Queue();
Queue after = new Queue();
// Traverse the array elements one by one
for (int i = 0; i < nums.Length; i++) {
// If the element is
// less than pivot range
// insert it into queue before
if (nums[i] < lowVal)
before.Enqueue(nums[i]);
// Else If the element is
// in between pivot range
// insert it into queue same
else if (nums[i] > highVal)
after.Enqueue(nums[i]);
// Else If the element is
// less than pivot range
// insert it into queue after
else
same.Enqueue(nums[i]);
}
int k = 0;
// Now insert all elements
// in queue before and
// insert into final vector
while (before.Count > 0) {
nums[k++] = (int)before.Peek();
before.Dequeue();
}
// Now insert all elements
// in queue same and
// insert into final vector
while (same.Count > 0) {
nums[k++] = (int)same.Peek();
same.Dequeue();
}
// Now insert all elements
// in queue after and
// insert into final vector
while (after.Count > 0) {
nums[k++] = (int)after.Peek();
after.Dequeue();
}
// Return the final vector
return nums;
}
// Driver code
static public void Main (){
int [ ] arr
= { 1, 14, 5, 20, 4, 2, 54,
20, 87, 98, 3, 1, 32 };
int lowVal = 20, highVal = 20;
pivotArray(arr, lowVal, highVal);
for (int i = 0; i < arr.Length; i++) {
Console.Write(arr[i] + " ");
}
}
}
// This code is contributed by hrithikgarg03188.
Javascript
<script>
// JavaScript code to implement three way
// partitioning of an array without
// changing the relative ordering
// Function to do three way partitioning
const pivotArray = (nums, lowVal, highVal) => {
// Declaring 3 queues
let before = [], same = [], after = [];
// Traverse the array elements one by one
for (let i = 0; i < nums.length; i++) {
// If the element is
// less than pivot range
// insert it into queue before
if (nums[i] < lowVal)
before.push(nums[i]);
// Else If the element is
// in between pivot range
// insert it into queue same
else if (nums[i] > highVal)
after.push(nums[i]);
// Else If the element is
// less than pivot range
// insert it into queue after
else
same.push(nums[i]);
}
let k = 0;
// Now insert all elements
// in queue before and
// insert into final vector
while (before.length > 0) {
nums[k++] = before[0];
before.shift();
}
// Now insert all elements
// in queue same and
// insert into final vector
while (same.length > 0) {
nums[k++] = same[0];
same.shift();
}
// Now insert all elements
// in queue after and
// insert into final vector
while (after.length > 0) {
nums[k++] = after[0];
after.shift();
}
// Return the final vector
return nums;
}
// Driver code
let arr = [1, 14, 5, 20, 4, 2, 54,
20, 87, 98, 3, 1, 32];
let lowVal = 20, highVal = 20;
pivotArray(arr, lowVal, highVal);
for (let i = 0; i < arr.length; i++) {
document.write(`${arr[i]} `);
}
// This code is contributed by rakeshsahni
</script>
Producción
1 14 5 4 2 3 1 20 20 54 87 98 32
Complejidad de tiempo: O(N), donde N es el tamaño de la array.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por krishmurarka y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA