Diberikan array angka, kembalikan array produk dari semua angka lain (tidak ada pembagian)

Saya ditanya pertanyaan ini dalam wawancara kerja, dan saya ingin tahu bagaimana orang lain akan menyelesaikannya. Saya paling nyaman dengan Java, tetapi solusi dalam bahasa lain dipersilahkan.

Diberikan array angka,, numskembalikan array angka products, di mana products[i]produk dari semua nums[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]

Anda harus melakukan ini O(N)tanpa menggunakan divisi.

Penjelasan metode polygenelubricants adalah: Caranya adalah dengan membangun array (dalam kasus untuk 4 elemen)

{              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,  }

Keduanya dapat dilakukan di O (n) dengan mulai masing-masing di tepi kiri dan kanan.

Kemudian mengalikan dua elemen array dengan elemen memberikan hasil yang diperlukan

Kode saya akan terlihat seperti ini:

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];
}

Jika Anda perlu menjadi O (1) di ruang angkasa juga Anda dapat melakukan ini (yang IMHO kurang jelas)

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];
}

Berikut adalah fungsi rekursif kecil (dalam C ++) untuk melakukan modofikasi di tempat. Ini membutuhkan O (n) ruang ekstra (on stack). Dengan asumsi array dalam a dan N memiliki panjang array, kita miliki

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;
}

Inilah upaya saya untuk menyelesaikannya di Jawa. Permintaan maaf untuk pemformatan non-standar, tetapi kode memiliki banyak duplikasi, dan ini adalah yang terbaik yang bisa saya lakukan untuk membuatnya dapat dibaca.

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]"
    }
}

Invarian loop adalah pi = nums[0] * nums[1] *.. nums[i-1]dan pj = nums[N-1] * nums[N-2] *.. nums[j+1]. Bagian idi sebelah kiri adalah logika "awalan", dan jbagian di sebelah kanan adalah logika "akhiran".

Satu liner rekursif

Jasmeet memberikan solusi rekursif (indah!); Saya telah mengubahnya menjadi ini (mengerikan!) Java one-liner. Itu modifikasi di tempat , dengan O(N)ruang sementara di stack.

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]"

Menerjemahkan solusi Michael Anderson ke dalam Haskell:

otherProducts xs = zipWith (*) below above

     where below = scanl (*) 1 $ init xs

           above = tail $ scanr (*) 1 xs

Secara diam-diam menghindari aturan "tidak ada pembagian":

sum = 0.0
for i in range(a):
  sum += log(a[i])

for i in range(a):
  output[i] = exp(sum - log(a[i]))

Ini dia, solusi sederhana dan bersih dengan kompleksitas 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]);
    }

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));

1. Bepergian Kiri-> Kanan dan simpan produk. Sebut Masa Lalu. -> O (n)
2. Bepergian Kanan -> kiri simpan produk. Sebut saja Masa Depan. -> O (n)
3. Hasil [i] = Melewati [i-1] * di masa depan [i + 1] -> O (n)
4. Melewati [-1] = 1; dan Masa Depan [n + 1] = 1;

Di)

Inilah solusi saya di C ++ modern. Itu memanfaatkan std::transformdan cukup mudah diingat.

Kode online (kotak suara).

#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 << " "; 
}

Ini O (n ^ 2) tetapi f # sangat indah:

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]

Hitung ulang produk angka di sebelah kiri dan di sebelah kanan setiap elemen. Untuk setiap elemen, nilai yang diinginkan adalah produk dari produk tetangga.

#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;
}

Hasil:

$ ./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

(PEMBARUAN: sekarang saya melihat lebih dekat, ini menggunakan metode yang sama seperti Michael Anderson, Daniel Migowski dan polygenelubricants di atas)

Rumit:

Gunakan yang berikut ini:

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];
}

Ya, saya yakin saya melewatkan beberapa i-1, bukan saya, tapi itulah cara untuk menyelesaikannya.

Ada juga solusi tidak optimal O (N ^ (3/2)) . Ini cukup menarik.

Pertama preprocess setiap perkalian parsial ukuran N ^ 0,5 (ini dilakukan dalam kompleksitas waktu O (N)). Kemudian, perhitungan untuk kelipatan nilai-nilai lain-setiap angka dapat dilakukan dalam waktu 2 * O (N ^ 0,5) (mengapa? Karena Anda hanya perlu melipatgandakan elemen terakhir dari nomor lainnya ((N ^ 0,5) - 1), dan kalikan hasilnya dengan ((N ^ 0,5) - 1) angka yang termasuk dalam kelompok nomor saat ini). Melakukan ini untuk setiap nomor, satu bisa mendapatkan O (N ^ (3/2)) waktu.

Contoh:

4 6 7 2 3 1 9 5 8

hasil parsial: 4 * 6 * 7 = 168 2 * 3 * 1 = 6 9 * 5 * 8 = 360

Untuk menghitung nilai 3, kita perlu melipatgandakan nilai kelompok lain 168 * 360, dan kemudian dengan 2 * 1.

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);
    }
}

Solusi ini saya buat dan saya merasa sangat jelas apa yang Anda pikirkan !?

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 = [] menghasilkan (arr, prod, 0) mencetak prod

Untuk menjadi lengkap di sini adalah kode dalam Scala:

val list1 = List(1, 2, 3, 4, 5)
for (elem <- list1) println(list1.filter(_ != elem) reduceLeft(_*_))

Ini akan mencetak yang berikut ini:

120
60
40
30
24

Program akan menyaring elem saat ini (_! = Elem); dan gandakan daftar baru dengan metode reduceLeft. Saya pikir ini akan menjadi O (n) jika Anda menggunakan tampilan scala atau Iterator untuk eval malas.

Berdasarkan jawaban Billz - maaf saya tidak bisa berkomentar, tapi di sini ada versi scala yang menangani item duplikat dengan benar, dan mungkin 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

pengembalian:

List(1008, 144, 336, 336, 252, 252)

Menambahkan solusi javascript saya di sini karena saya tidak menemukan orang menyarankan ini. Apa yang harus dibagi, kecuali untuk menghitung berapa kali Anda dapat mengekstraksi angka dari nomor lain? Saya menghitung produk seluruh array, dan kemudian beralih ke setiap elemen, dan mengurangi elemen saat ini sampai nol:

//No division operation allowed
// keep substracting divisor from dividend, until dividend is zero or less than divisor
function calculateProducsExceptCurrent_NoDivision(input){
  var res = [];
  var totalProduct = 1;
  //calculate the total product
  for(var i = 0; i < input.length; i++){
    totalProduct = totalProduct * input[i];
  }
  //populate the result array by "dividing" each value
  for(var i = 0; i < input.length; i++){
    var timesSubstracted = 0;
    var divisor = input[i];
    var dividend = totalProduct;
    while(divisor <= dividend){
      dividend = dividend - divisor;
      timesSubstracted++;
    }
    res.push(timesSubstracted);
  }
  return res;
}

Saya gunakan untuk C #:

    public int[] ProductExceptSelf(int[] nums)
    {
        int[] returnArray = new int[nums.Length];
        List<int> auxList = new List<int>();
        int multTotal = 0;

        // If no zeros are contained in the array you only have to calculate it once
        if(!nums.Contains(0))
        {
            multTotal = nums.ToList().Aggregate((a, b) => a * b);

            for (int i = 0; i < nums.Length; i++)
            {
                returnArray[i] = multTotal / nums[i];
            }
        }
        else
        {
            for (int i = 0; i < nums.Length; i++)
            {
                auxList = nums.ToList();
                auxList.RemoveAt(i);
                if (!auxList.Contains(0))
                {
                    returnArray[i] = auxList.Aggregate((a, b) => a * b);
                }
                else
                {
                    returnArray[i] = 0;
                }
            }
        }            

        return returnArray;
    }

Kita dapat mengecualikan nums[j](di mana j != i) dari daftar terlebih dahulu, lalu mendapatkan produk sisanya; Berikut ini adalah python wayuntuk menyelesaikan puzzle ini:

from functools import reduce
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]

Nah, solusi ini dapat dianggap sebagai C / C ++. Katakanlah kita memiliki array "a" yang mengandung n elemen seperti [n], maka kode pseudo akan seperti di bawah ini.

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];
  }

Satu lagi solusi, Menggunakan pembagian. dengan dua kali traversal. Lipat gandakan semua elemen dan kemudian mulai membaginya dengan setiap elemen.

{-
Solusi rekursif menggunakan himpunan bagian sqrt (n). Berjalan di O (n).

Secara rekursif menghitung solusi pada sqrt (n) himpunan bagian dari ukuran sqrt (n). 
Kemudian berulang pada jumlah produk setiap subset.
Kemudian untuk setiap elemen di setiap subset, itu menghitung produk dengan
jumlah produk semua produk lainnya.
Lalu ratakan semua himpunan bagian.

Perulangan pada waktu berjalan adalah T (n) = sqrt (n) * T (sqrt (n)) + T (sqrt (n)) + n

Misalkan T (n) ≤ cn dalam 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)

Perhatikan bahwa plafon (sqrt (n)) dapat dihitung menggunakan pencarian biner 
dan iterasi O (logn), jika instruksi sqrt tidak diizinkan.
-}

otherProducts [] = []
otherProducts [x] = [1]
otherProducts [x, y] = [y, x]
otherProducts a = foldl '(++) [] $ zipWith (\ sp -> map (* p) s) diselesaikanSubsets subsetOtherProducts
    dimana 
      n = panjang a

      - Ukuran subset. Mensyaratkan bahwa 1 <s <n.
      s = ceiling $ sqrt $ fromIntegral n

      diselesaikanSubsets = petakan map otherProducts
      subsetOtherProducts = otherProducts $ map subset produk

      himpunan bagian = membalikkan $ loop a []
          di mana loop [] acc = acc
                loop a acc = loop (drop sa) ((take sa): acc)

Ini kode saya:

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;
}

Berikut ini contoh yang sedikit fungsional, menggunakan 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]();
                }
            }

Saya tidak sepenuhnya yakin bahwa ini adalah O (n), karena semi-rekursi dari Funcs yang dibuat, tetapi tes saya tampaknya menunjukkan bahwa itu O (n) pada waktunya.

// Ini adalah solusi rekursif di Jawa // Disebut sebagai berikut dari produk utama (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;
}

Solusi yang rapi dengan runtime O (n):

1. Untuk setiap elemen, hitung produk dari semua elemen yang terjadi sebelum itu dan simpan dalam array "pre".
2. Untuk setiap elemen, hitung produk semua elemen yang terjadi setelah elemen itu dan simpan dalam "posting" array

3. Buat array akhir "hasil", untuk elemen i,

   result[i] = pre[i-1]*post[i+1];
   

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));

Berikut ini adalah konsep sederhana lain yang memecahkan masalah di 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));

Saya punya solusi dengan kompleksitas O(n)ruang dan O(n^2)waktu yang disediakan di bawah ini,

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;
    }