Dada una array arr que consta de N enteros y un entero K , la tarea es insertar una K adyacente para cada ocurrencia en la secuencia original y luego truncar la array a la longitud original usando un espacio auxiliar O(1).
Ejemplos:
Entrada: arr[] = {1, 0, 2, 3, 0, 4, 5, 0}, K = 0
Salida: {1, 0, 0, 2, 3, 0, 0, 4}
Explicación:
El dado la array {1, 0, 2, 3, 0, 4, 5, 0} se modifica a {1, 0, 0 , 2, 3, 0, 0 , 4] después de la inserción de dos 0 y el truncamiento de elementos adicionales.Entrada: arr[] = {7, 5, 8}, K = 8
Salida: {7, 5, 8}
Explicación:
después de insertar un 8 adyacente en la array, se truncó para restaurar el tamaño original de la array.
Enfoque 1: Usar funciones STL
Este problema se puede resolver usando las funciones integradas pop_back() e insert() .
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ implementation to update each entry of k
// with two k entries adjacent to each other
#include <bits/stdc++.h>
using namespace std;
// Function to update each entry of k
// with two k entries adjacent to each other
void duplicateK(vector<int>& arr,int& k)
{
int N = arr.size();
for(int i=0;i<N;i++)
{
if(arr[i] == k)
{
// Insert an adjacent k
arr.insert(arr.begin() + i + 1, k);
i++;
// Pop the last element
arr.pop_back();
}
}
}
// Driver code
int main(int argc, char* argv[])
{
vector<int> arr
= { 1, 0, 2, 3, 0, 4, 5, 0 };
int k=0;
duplicateK(arr,k);
for (int i = 0; i < arr.size(); i++)
cout << arr[i] << " ";
return 0;
}
Java
// Java implementation to update each
// entry of k with two k entries
// adjacent to each other
import java.util.*;
class GFG{
// Function to update each entry of
// k with two k entries
// adjacent to each other
static Vector<Integer> duplicateK(Vector<Integer> arr,int k)
{
int N = arr.size();
for(int i = 0; i < N; i++)
{
if(arr.get(i) == k)
{
// Insert an adjacent k
arr.add(i + 1, k);
i++;
// Pop the last element
arr.remove(arr.size() - 1);
}
}
return arr;
}
// Driver code
public static void main(String[] args)
{
Integer []arr = { 1, 0, 2, 3, 0, 4, 5, 0 };
Vector<Integer> vec = new Vector<Integer>();;
for(int i = 0; i < arr.length; i++)
vec.add(arr[i]);
int k=0;
Vector<Integer> ans = duplicateK(vec,k);
for(int i = 0; i < ans.size(); i++)
System.out.print(ans.get(i) + " ");
}
}
// This code is contributed by gauravrajput1
Python3
# python3 implementation to update each entry of k # with two k entries adjacent to each other # Function to update each entry of k # with two k entries adjacent to each other def duplicateK(arr, k): N = len(arr) i = 0 while(i < N): if(arr[i] == k): # Insert an adjacent k arr.insert(i + 1, k) i += 1 # Pop the last element arr.pop() i += 1 # Driver code if __name__ == "__main__": arr = [1, 0, 2, 3, 0, 4, 5, 0] k = 0 duplicateK(arr, k) for i in range(0, len(arr)): print(arr[i], end=" ") # This code is contributed by rakeshsahni
C#
// C# implementation to update each
// entry of k with two k entries
// adjacent to each other
using System;
using System.Collections.Generic;
class GFG{
// Function to update each entry of
// k with two k entries
// adjacent to each other
static List<int> duplicateK(List<int> arr,int k)
{
int N = arr.Count;
for(int i = 0; i < N; i++)
{
if(arr[i] == k)
{
// Insert an adjacent k
arr.Insert(i + 1, k);
i++;
// Pop the last element
arr.RemoveAt(arr.Count - 1);
}
}
return arr;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 1, 0, 2, 3, 0, 4, 5, 0 };
int k=0;
List<int> vec = new List<int>();;
for(int i = 0; i < arr.Length; i++)
vec.Add(arr[i]);
List<int> ans = duplicateK(vec,k);
for(int i = 0; i < ans.Count; i++)
Console.Write(ans[i] + " ");
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript implementation to update each entry of k
// with two k entries adjacent to each other
// Function to update each entry of k
// with two k entries adjacent to each other
function duplicateK(arr,k)
{
var N = arr.length;
for(var i=0;i<N;i++)
{
if(arr[i] == k)
{
// Insert an adjacent k
arr.splice(i+1, 0, k);
i++;
// Pop the last element
arr.pop();
}
}
return arr;
}
// Driver code
var arr=[ 1, 0, 2, 3, 0, 4, 5, 0 ];
var k=0;
var ans = duplicateK(arr,k);
for (var i = 0; i < ans.length; i++)
document.write(ans[i] + " ");
</script>
Producción:
1 0 0 2 3 0 0 4
Enfoque 2: Uso de la técnica de dos punteros
- Dado que cada K debe actualizarse con dos K entradas adyacentes entre sí, la array aumentará en longitud en una cantidad igual al número de K que están presentes en la array original arr[].
- Encuentre el número total de K, luego asumimos que tenemos una array con suficiente espacio para acomodar cada elemento.
- Inicialice una variable write_idx que apuntará al índice al final de esta array imaginaria y otro puntero curr al final de la array actual, que es arr[N-1].
- Iterar desde el final y para cada elemento asumimos que estamos copiando el elemento a su posición actual, pero copiar solo si write_idx < N, y seguir actualizando write_idx cada vez. Para un elemento con un valor de cero, escríbalo dos veces.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ implementation to update each entry of k
// with two k entries adjacent to each other
#include <bits/stdc++.h>
using namespace std;
// Function to update each entry of k
// with two k entries adjacent to each other
vector<int> duplicateK(vector<int>& arr,int k)
{
const int N = arr.size();
// Find the count of total number of k
int cnt = count(arr.begin(), arr.end(), k);
// Variable to store index where elements
// will be written in the final array
int write_idx = N + cnt - 1;
// Variable to point the current index
int curr = N - 1;
while (curr >= 0 && write_idx >= 0) {
// Keep the current element to its correct
// position, if that is within the size N
if (write_idx < N)
arr[write_idx] = arr[curr];
write_idx -= 1;
// Check if the current element is also
// k then again write its duplicate
if (arr[curr] == k) {
if (write_idx < N)
arr[write_idx] = k;
write_idx -= 1;
}
--curr;
}
// Return the final result
return arr;
}
// Driver code
int main(int argc, char* argv[])
{
vector<int> arr = { 1, 0, 2, 3, 0, 4, 5, 0 };
int k=0;
vector<int> ans = duplicateK(arr,k);
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << " ";
return 0;
}
Java
// Java implementation to update
// each entry of k with two k
// entries adjacent to each other
class GFG{
// Function to update each
// entry of k with two k
// entries adjacent to each other
static int[] duplicateK(int []arr,int k)
{
int N = arr.length;
// Find the count of
// total number of k
int cnt = count(arr, k);
// Variable to store index
// where elements will be
// written in the final array
int write_idx = N + cnt - 1;
// Variable to point the current index
int curr = N - 1;
while (curr >= 0 && write_idx >= 0)
{
// Keep the current element
// to its correctposition, if
// that is within the size N
if (write_idx < N)
arr[write_idx] = arr[curr];
write_idx -= 1;
// Check if the current element is also
// k then again write its duplicate
if (arr[curr] == k)
{
if (write_idx < N)
arr[write_idx] = k;
write_idx -= 1;
}
--curr;
}
// Return the final result
return arr;
}
static int count(int []arr, int num)
{
int ans = 0;
for(int i : arr)
if(i == num)
ans++;
return ans;
}
// Driver code
public static void main(String[] args)
{
int []arr = { 1, 0, 2, 3, 0, 4, 5, 0 };
int k=0;
int []ans = duplicateK(arr,k);
for(int i = 0; i < ans.length; i++)
System.out.print(ans[i] + " ");
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 implementation to update each entry of k # with two k entries adjacent to each other # Function to update each entry of k # with two k entries adjacent to each other def duplicateK(arr,k): N = len(arr) # Find the count of total number of k cnt = arr.count(k) # Variable to store index where elements # will be written in the final array write_idx = N + cnt - 1 # Variable to point the current index curr = N - 1 while (curr >= 0 and write_idx >= 0): # Keep the current element to its correct # position, if that is within the size N if (write_idx < N): arr[write_idx] = arr[curr] write_idx -= 1 # Check if the current element is also # k then again write its duplicate if (arr[curr] == k): if (write_idx < N): arr[write_idx] = k write_idx -= 1 curr -= 1 # Return the final result return arr # Driver Code arr = [ 1, 0, 2, 3, 0, 4, 5, 0 ] k=0 ans = duplicateK(arr,k) for i in range(len(ans)): print(ans[i], end = " ") # This code is contributed by divyamohan123
C#
// C# implementation to update
// each entry of k with two k
// entries adjacent to each other
using System;
class GFG{
// Function to update each
// entry of k with two k
// entries adjacent to each other
static int[] duplicateK(int []arr,int k)
{
int N = arr.Length;
// Find the count of
// total number of k
int cnt = count(arr, k);
// Variable to store index
// where elements will be
// written in the readonly array
int write_idx = N + cnt - 1;
// Variable to point the
// current index
int curr = N - 1;
while (curr >= 0 && write_idx >= 0)
{
// Keep the current element
// to its correctposition, if
// that is within the size N
if (write_idx < N)
arr[write_idx] = arr[curr];
write_idx -= 1;
// Check if the current element is also
// k then again write its duplicate
if (arr[curr] == k)
{
if (write_idx < N)
arr[write_idx] = k;
write_idx -= 1;
}
--curr;
}
// Return the readonly result
return arr;
}
static int count(int []arr, int num)
{
int ans = 0;
foreach(int i in arr)
{
if(i == num)
ans++;
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 1, 0, 2, 3, 0, 4, 5, 0 };
int k=0;
int []ans = duplicateK(arr,k);
for(int i = 0; i < ans.Length; i++)
Console.Write(ans[i] + " ");
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript implementation to update each entry of k
// with two k entries adjacent to each other
// Function to update each entry of k
// with two k entries adjacent to each other
function duplicateK(arr,k)
{
const N = arr.length;
// Find the count of total number of k
let cnt = 0;
for(let i = 0; i < arr.length; ++i){
if(arr[i] == k)
cnt++;
}
// Variable to store index where elements
// will be written in the final array
let write_idx = N + cnt - 1;
// Variable to point the current index
let curr = N - 1;
while (curr >= 0 && write_idx >= 0) {
// Keep the current element to its correct
// position, if that is within the size N
if (write_idx < N)
arr[write_idx] = arr[curr];
write_idx -= 1;
// Check if the current element is also
// k then again write its duplicate
if (arr[curr] == k) {
if (write_idx < N)
arr[write_idx] = k;
write_idx -= 1;
}
--curr;
}
// Return the final result
return arr;
}
// Driver code
let arr = [ 1, 0, 2, 3, 0, 4, 5, 0 ];
let k=0;
let ans = duplicateK(arr,k);
for (let i = 0; i < ans.length; i++)
document.write(ans[i] + " ");
// This code is contributed by Surbhi Tyagi.
</script>
Producción:
1 0 0 2 3 0 0 4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)