arrays - resueltos - vectores y matrices en programacion
Dada una matriz de números, devuelve un conjunto de productos de todos los demás números(sin división) (30)
- Viaja hacia la izquierda y hacia la derecha y sigue guardando el producto. Llámalo Pasado. -> O (n)
- Viaje a la derecha -> a la izquierda, guarde el producto. Llámalo Futuro. -> O (n)
- Resultado [i] = Pasado [i-1] * futuro [i + 1] -> O (n)
- Pasado [-1] = 1; y Futuro [n + 1] = 1;
En)
Me hicieron esta pregunta en una entrevista de trabajo y me gustaría saber cómo lo resolverían otros. Estoy más cómodo con Java, pero las soluciones en otros idiomas son bienvenidas.
Dada una serie de números,
nums, devuelve una matriz de númerosproducts, donde losproducts[i]son el producto de todos losnums[j], j != i
Input : [1, 2, 3, 4, 5] Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)] = [120, 60, 40, 30, 24]Debes hacer esto en
O(N)sin usar la división.
// Esta es la solución recursiva en Java // Llamada como siguiente del producto principal (a, 1,0);
public static double product(double[] a, double fwdprod, int index){
double revprod = 1;
if (index < a.length){
revprod = product2(a, fwdprod*a[index], index+1);
double cur = a[index];
a[index] = fwdprod * revprod;
revprod *= cur;
}
return revprod;
}
Aquí está la versión de ptyhon
# This solution use O(n) time and O(n) space
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
N = len(nums)
if N == 0: return
# Initialzie list of 1, size N
l_prods, r_prods = [1]*N, [1]*N
for i in range(1, N):
l_prods[i] = l_prods[i-1] * nums[i-1]
for i in reversed(range(N-1)):
r_prods[i] = r_prods[i+1] * nums[i+1]
result = [x*y for x,y in zip(l_prods,r_prods)]
return result
# This solution use O(n) time and O(1) space
def productExceptSelfSpaceOptimized(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
N = len(nums)
if N == 0: return
# Initialzie list of 1, size N
result = [1]*N
for i in range(1, N):
result[i] = result[i-1] * nums[i-1]
r_prod = 1
for i in reversed(range(N)):
result[i] *= r_prod
r_prod *= nums[i]
return result
Aquí está mi código:
int multiply(int a[],int n,int nextproduct,int i)
{
int prevproduct=1;
if(i>=n)
return prevproduct;
prevproduct=multiply(a,n,nextproduct*a[i],i+1);
printf(" i=%d > %d/n",i,prevproduct*nextproduct);
return prevproduct*a[i];
}
int main()
{
int a[]={2,4,1,3,5};
multiply(a,5,1,0);
return 0;
}
Aquí está mi intento de resolverlo en Java. Disculpas por el formato no estándar, pero el código tiene mucha duplicación, y esto es lo mejor que puedo hacer para que sea legible.
import java.util.Arrays;
public class Products {
static int[] products(int... nums) {
final int N = nums.length;
int[] prods = new int[N];
Arrays.fill(prods, 1);
for (int
i = 0, pi = 1 , j = N-1, pj = 1 ;
(i < N) && (j >= 0) ;
pi *= nums[i++] , pj *= nums[j--] )
{
prods[i] *= pi ; prods[j] *= pj ;
}
return prods;
}
public static void main(String[] args) {
System.out.println(
Arrays.toString(products(1, 2, 3, 4, 5))
); // prints "[120, 60, 40, 30, 24]"
}
}
Las invariantes de bucle son pi = nums[0] * nums[1] *.. nums[i-1] y pj = nums[N-1] * nums[N-2] *.. nums[j+1] . La parte i a la izquierda es la lógica del "prefijo", y la parte j a la derecha es la lógica del "sufijo".
Recursivo de una sola línea
Jasmeet dio una (¡hermosa!) Solución recursiva; Lo he convertido en este (horrible!) Java one-liner. Hace una modificación in situ , con O(N) espacio temporal en la pila.
static int multiply(int[] nums, int p, int n) {
return (n == nums.length) ? 1
: nums[n] * (p = multiply(nums, nums[n] * (nums[n] = p), n + 1))
+ 0*(nums[n] *= p);
}
int[] arr = {1,2,3,4,5};
multiply(arr, 1, 0);
System.out.println(Arrays.toString(arr));
// prints "[120, 60, 40, 30, 24]"
Aquí está mi solución en C ++ moderno. Hace uso de std::transform y es bastante fácil de recordar.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
vector<int>& multiply_up(vector<int>& v){
v.insert(v.begin(),1);
transform(v.begin()+1, v.end()
,v.begin()
,v.begin()+1
,[](auto const& a, auto const& b) { return b*a; }
);
v.pop_back();
return v;
}
int main() {
vector<int> v = {1,2,3,4,5};
auto vr = v;
reverse(vr.begin(),vr.end());
multiply_up(v);
multiply_up(vr);
reverse(vr.begin(),vr.end());
transform(v.begin(),v.end()
,vr.begin()
,v.begin()
,[](auto const& a, auto const& b) { return b*a; }
);
for(auto& i: v) cout << i << " ";
}
Aquí hay otro concepto simple que resuelve el problema en O(N) .
int[] arr = new int[] {1, 2, 3, 4, 5};
int[] outArray = new int[arr.length];
for(int i=0;i<arr.length;i++){
int res=Arrays.stream(arr).reduce(1, (a, b) -> a * b);
outArray[i] = res/arr[i];
}
System.out.println(Arrays.toString(outArray));
Aquí hay un ejemplo ligeramente funcional, usando C #:
Func<long>[] backwards = new Func<long>[input.Length];
Func<long>[] forwards = new Func<long>[input.Length];
for (int i = 0; i < input.Length; ++i)
{
var localIndex = i;
backwards[i] = () => (localIndex > 0 ? backwards[localIndex - 1]() : 1) * input[localIndex];
forwards[i] = () => (localIndex < input.Length - 1 ? forwards[localIndex + 1]() : 1) * input[localIndex];
}
var output = new long[input.Length];
for (int i = 0; i < input.Length; ++i)
{
if (0 == i)
{
output[i] = forwards[i + 1]();
}
else if (input.Length - 1 == i)
{
output[i] = backwards[i - 1]();
}
else
{
output[i] = forwards[i + 1]() * backwards[i - 1]();
}
}
No estoy del todo seguro de que esto sea O (n), debido a la semi-recursión de los Funcs creados, pero mis pruebas parecen indicar que es O (n) en el tiempo.
Aquí hay una pequeña función recursiva (en C ++) para hacer la modificación en su lugar. Sin embargo, requiere O (n) espacio extra (en la pila). Suponiendo que la matriz está en ay N tiene la longitud de la matriz, tenemos
int multiply(int *a, int fwdProduct, int indx) {
int revProduct = 1;
if (indx < N) {
revProduct = multiply(a, fwdProduct*a[indx], indx+1);
int cur = a[indx];
a[indx] = fwdProduct * revProduct;
revProduct *= cur;
}
return revProduct;
}
Aquí tienes, solución simple y limpia con complejidad O (N):
int[] a = {1,2,3,4,5};
int[] r = new int[a.length];
int x = 1;
r[0] = 1;
for (int i=1;i<a.length;i++){
r[i]=r[i-1]*a[i-1];
}
for (int i=a.length-1;i>0;i--){
x=x*a[i];
r[i-1]=x*r[i-1];
}
for (int i=0;i<r.length;i++){
System.out.println(r[i]);
}
Basado en la respuesta de Billz: lo siento, no puedo comentar, pero aquí hay una versión de Scala que maneja correctamente los elementos duplicados en la lista, y probablemente sea O (n):
val list1 = List(1, 7, 3, 3, 4, 4)
val view = list1.view.zipWithIndex map { x => list1.view.patch(x._2, Nil, 1).reduceLeft(_*_)}
view.force
devoluciones:
List(1008, 144, 336, 336, 252, 252)
Bueno, esta solución se puede considerar la de C / C ++. Digamos que tenemos una matriz "a" que contiene n elementos como a [n], y luego el pseudo código sería el siguiente.
for(j=0;j<n;j++)
{
prod[j]=1;
for (i=0;i<n;i++)
{
if(i==j)
continue;
else
prod[j]=prod[j]*a[i];
}
C ++, O (n):
long long prod = accumulate(in.begin(), in.end(), 1LL, multiplies<int>());
transform(in.begin(), in.end(), back_inserter(res),
bind1st(divides<long long>(), prod));
Difícil:
Use lo siguiente:
public int[] calc(int[] params) {
int[] left = new int[n-1]
in[] right = new int[n-1]
int fac1 = 1;
int fac2 = 1;
for( int i=0; i<n; i++ ) {
fac1 = fac1 * params[i];
fac2 = fac2 * params[n-i];
left[i] = fac1;
right[i] = fac2;
}
fac = 1;
int[] results = new int[n];
for( int i=0; i<n; i++ ) {
results[i] = left[i] * right[i];
}
Sí, estoy seguro de haber perdido algo de i-1 en lugar de i, pero esa es la manera de resolverlo.
Este es O (n ^ 2) pero f # es tan hermoso:
List.fold (fun seed i -> List.mapi (fun j x -> if i=j+1 then x else x*i) seed)
[1;1;1;1;1]
[1..5]
Me hicieron esta pregunta recientemente, y aunque no pude obtener O (N) durante el mismo, tuve un enfoque diferente (desafortunadamente O (N ^ 2)) pero pensé que lo compartiría de todos modos.
Convertir a la List<Integer> primero.
array.length() por la matriz original array.length() veces.
Use un ciclo while para multiplicar el siguiente conjunto de números requeridos:
while (temp < list.size() - 1) {
res *= list.get(temp);
temp++;
}
A continuación, agregue res a una nueva matriz (que por supuesto ha declarado anteriormente), luego agregue el valor en la array[i] a la List , y continúe así.
Sé que esto no será de gran utilidad, pero es lo que surgió bajo las presiones de una entrevista :)
int[] array = new int[]{1, 2, 3, 4, 5};
List<Integer> list = Arrays.stream(array).boxed().collect(Collectors.toList());
int[] newarray = new int[array.length];
int res = 1;
for (int i = 0; i < array.length; i++) {
int temp = i;
while (temp < list.size() - 1) {
res *= list.get(temp);
temp++;
}
newarray[i] = res;
list.add(array[i]);
res = 1;
}
Salida: [24, 120, 60, 40, 30]
Para completar aquí está el código en Scala:
val list1 = List(1, 2, 3, 4, 5)
for (elem <- list1) println(list1.filter(_ != elem) reduceLeft(_*_))
Esto imprimirá lo siguiente:
120
60
40
30
24
El programa filtrará el elemento actual (_! = Elem); y multiplique la nueva lista con el método reductionLeft. Creo que esto será O (n) si usa scala view o Iterator para lazy eval.
Podemos excluir los nums[j] (donde j != i ) de la lista primero, luego obtener el producto del resto; La siguiente es una python way para resolver este rompecabezas:
def products(nums):
return [ reduce(lambda x,y: x * y, nums[:i] + nums[i+1:]) for i in range(len(nums)) ]
print products([1, 2, 3, 4, 5])
[out]
[120, 60, 40, 30, 24]
Precalcular el producto de los números a la izquierda y a la derecha de cada elemento. Para cada elemento, el valor deseado es el producto de sus productos.
#include <stdio.h>
unsigned array[5] = { 1,2,3,4,5};
int main(void)
{
unsigned idx;
unsigned left[5]
, right[5];
left[0] = 1;
right[4] = 1;
/* calculate products of numbers to the left of [idx] */
for (idx=1; idx < 5; idx++) {
left[idx] = left[idx-1] * array[idx-1];
}
/* calculate products of numbers to the right of [idx] */
for (idx=4; idx-- > 0; ) {
right[idx] = right[idx+1] * array[idx+1];
}
for (idx=0; idx <5 ; idx++) {
printf("[%u] Product(%u*%u) = %u/n"
, idx, left[idx] , right[idx] , left[idx] * right[idx] );
}
return 0;
}
Resultado:
$ ./a.out
[0] Product(1*120) = 120
[1] Product(1*60) = 60
[2] Product(2*20) = 40
[3] Product(6*5) = 30
[4] Product(24*1) = 24
(ACTUALIZACIÓN: ahora miro más de cerca, esto utiliza el mismo método que Michael Anderson, Daniel Migowski y polygenelubricants arriba)
Sneakily eludir la regla de "no divisiones":
sum = 0.0
for i in range(a):
sum += log(a[i])
for i in range(a):
output[i] = exp(sum - log(a[i]))
También hay una solución no óptima O (N ^ (3/2)). Sin embargo, es bastante interesante.
Primero preprocesé cada multiplicación parcial de tamaño N ^ 0.5 (esto se hace en O (N) complejidad de tiempo). Entonces, el cálculo de los valores-otros-de cada número se puede hacer en 2 * O (N ^ 0.5) veces (¿por qué? Porque solo necesita multiplicar los últimos elementos de otros ((N ^ 0.5) - 1) números, y multiplica el resultado con ((N ^ 0.5) - 1) números que pertenecen al grupo del número actual). Haciendo esto para cada número, uno puede obtener O (N ^ (3/2)) tiempo.
Ejemplo:
4 6 7 2 3 1 9 5 8
resultados parciales: 4 * 6 * 7 = 168 2 * 3 * 1 = 6 9 * 5 * 8 = 360
Para calcular el valor de 3, se necesita multiplicar los valores de los otros grupos 168 * 360, y luego con 2 * 1.
Tengo una solución con O(n) espacio y O(n^2) complejidad de tiempo proporcionada a continuación,
public static int[] findEachElementAsProduct1(final int[] arr) {
int len = arr.length;
// int[] product = new int[len];
// Arrays.fill(product, 1);
int[] product = IntStream.generate(() -> 1).limit(len).toArray();
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
if (i == j) {
continue;
}
product[i] *= arr[j];
}
}
return product;
}
Traduciendo la solución de Michael Anderson en Haskell:
otherProducts xs = zipWith (*) below above
where below = scanl (*) 1 $ init xs
above = tail $ scanr (*) 1 xs
Una explicación del método es: El truco es construir las matrices (en el caso de 4 elementos)
{ 1, a[0], a[0]*a[1], a[0]*a[1]*a[2], }
{ a[1]*a[2]*a[3], a[2]*a[3], a[3], 1, }
Ambos se pueden hacer en O (n) comenzando por los bordes izquierdo y derecho, respectivamente.
Luego, multiplicando los dos arrays elemento por elemento da el resultado requerido
Mi código se vería así:
int a[N] // This is the input
int products_below[N];
p=1;
for(int i=0;i<N;++i) {
products_below[i]=p;
p*=a[i];
}
int products_above[N];
p=1;
for(int i=N-1;i>=0;--i) {
products_above[i]=p;
p*=a[i];
}
int products[N]; // This is the result
for(int i=0;i<N;++i) {
products[i]=products_below[i]*products_above[i];
}
Si necesita ser O (1) en el espacio también puede hacer esto (que es menos claro en mi humilde opinión)
int a[N] // This is the input
int products[N];
// Get the products below the current index
p=1;
for(int i=0;i<N;++i) {
products[i]=p;
p*=a[i];
}
// Get the products above the curent index
p=1;
for(int i=N-1;i>=0;--i) {
products[i]*=p;
p*=a[i];
}
Una solución más, usando la división. con dos travesías. Multiplica todos los elementos y luego comienza a dividirlos por cada elemento.
Una solución ordenada con tiempo de ejecución O (n):
- Para cada elemento, calcule el producto de todos los elementos que ocurren antes de eso y almacene en una matriz "pre".
- Para cada elemento, calcule el producto de todos los elementos que ocurren después de ese elemento y guárdelo en una matriz "publicar"
Crea un "resultado" de matriz final, para un elemento i,
result[i] = pre[i-1]*post[i+1];
{- Recursive solution using sqrt(n) subsets. Runs in O(n). Recursively computes the solution on sqrt(n) subsets of size sqrt(n). Then recurses on the product sum of each subset. Then for each element in each subset, it computes the product with the product sum of all other products. Then flattens all subsets. Recurrence on the run time is T(n) = sqrt(n)*T(sqrt(n)) + T(sqrt(n)) + n Suppose that T(n) ≤ cn in O(n). T(n) = sqrt(n)*T(sqrt(n)) + T(sqrt(n)) + n ≤ sqrt(n)*c*sqrt(n) + c*sqrt(n) + n ≤ c*n + c*sqrt(n) + n ≤ (2c+1)*n ∈ O(n) Note that ceiling(sqrt(n)) can be computed using a binary search and O(logn) iterations, if the sqrt instruction is not permitted. -} otherProducts [] = [] otherProducts [x] = [1] otherProducts [x,y] = [y,x] otherProducts a = foldl'' (++) [] $ zipWith (/s p -> map (*p) s) solvedSubsets subsetOtherProducts where n = length a -- Subset size. Require that 1 < s < n. s = ceiling $ sqrt $ fromIntegral n solvedSubsets = map otherProducts subsets subsetOtherProducts = otherProducts $ map product subsets subsets = reverse $ loop a [] where loop [] acc = acc loop a acc = loop (drop s a) ((take s a):acc)
def productify(arr, prod, i):
if i < len(arr):
prod.append(arr[i - 1] * prod[i - 1]) if i > 0 else prod.append(1)
retval = productify(arr, prod, i + 1)
prod[i] *= retval
return retval * arr[i]
return 1
arr = [1, 2, 3, 4, 5] prod = [] productify (arr, prod, 0) imprimir prod
function solution($array)
{
$result = [];
foreach($array as $key => $value){
$copyOfOriginalArray = $array;
unset($copyOfOriginalArray[$key]);
$result[$key] = multiplyAllElemets($copyOfOriginalArray);
}
return $result;
}
/**
* multiplies all elements of array
* @param $array
* @return int
*/
function multiplyAllElemets($array){
$result = 1;
foreach($array as $element){
$result *= $element;
}
return $result;
}
$array = [1, 9, 2, 7];
print_r(solution($array));
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 4, 5 };
int[] result = { 1, 1, 1, 1, 1 };
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
result[i] *= arr[j];
}
for (int k = arr.length - 1; k > i; k--) {
result[i] *= arr[k];
}
}
for (int i : result) {
System.out.println(i);
}
}
Se me ocurrió esta solución y la encontré tan clara ¿qué opinas?