第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號安全，請及時綁定郵箱和手機立即綁定
已解決430363個問題，去搜搜看，總會有你想問的

給定一組數(shù)字，返回所有其他數(shù)字的產(chǎn)品數(shù)組（無分區(qū)）

給定一組數(shù)字，返回所有其他數(shù)字的產(chǎn)品數(shù)組（無分區(qū)）

我在求職面試中被問到這個問題，我想知道其他人如何解決這個問題。我對Java最熟悉，但歡迎使用其他語言的解決方案。給定一組數(shù)字，nums返回一個數(shù)字?jǐn)?shù)組products，其中products[i]是所有數(shù)字的乘積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]你必須在O(N)不使用除法的情況下這樣做。
查看完整描述

3 回答

?
開心每一天1111

TA貢獻1836條經(jīng)驗 獲得超13個贊

polygenelubricants方法的解釋是：訣竅是構(gòu)造數(shù)組（在4個元素的情況下）

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

通過分別從左邊緣和右邊緣開始，可以在O（n）中完成這兩個操作。


然后將兩個數(shù)組逐個元素相乘，得到所需的結(jié)果


我的代碼看起來像這樣：


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

}

如果你需要在太空中是O（1）你也可以這樣做（這不太清楚恕我直言）


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

}


查看完整回答
反對 回復(fù) 2019-09-18
?
天涯盡頭無女友

TA貢獻1831條經(jīng)驗 獲得超9個贊

這是一個小的遞歸函數(shù)（在C ++中）來進行修改。它需要O（n）額外空間（在堆棧上）。假設(shè)數(shù)組在a中并且N保持?jǐn)?shù)組長度，我們有


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;

}


查看完整回答
反對 回復(fù) 2019-09-18
?
慕神8447489

TA貢獻1780條經(jīng)驗 獲得超1個贊

這是我嘗試用Java解決它。抱歉為非標(biāo)準(zhǔn)格式化，但代碼有很多重復(fù)，這是我能做的最好的，使它可讀。


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

    }

}

循環(huán)不變量是pi = nums[0] * nums[1] *.. nums[i-1]和pj = nums[N-1] * nums[N-2] *.. nums[j+1]。i左邊的部分是“前綴”邏輯，j右邊的部分是“后綴”邏輯。


遞歸單行

Jasmeet給出了一個（漂亮?。┻f歸解決方案; 我把它變成了這個（丑陋的）Java單線程。它使用堆棧中的臨時空間進行就地修改O(N)。


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


查看完整回答
反對 回復(fù) 2019-09-18
  • 3 回答
  • 0 關(guān)注
  • 751 瀏覽

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯(lián)系客服咨詢優(yōu)惠詳情

 幫助反饋 APP下載

慕課網(wǎng)APP
您的移動學(xué)習(xí)伙伴

 公眾號

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號