10

重複の可能性：
インタビューQ：数値の配列が与えられた場合、他のすべての数値の積の配列を返します（除算なし）

2つの配列がinputArrayあり、それぞれresultArrayにn要素があります。
タスクは、のn番目の要素が（すべての要素の）のn番目の要素を除くresultArrayすべての要素の乗算を持つ必要があることです。 例えば。 それなら これは簡単です...inputArrayinputArrayn-1
inputArray={1,2,3,4}
resultArray={24,12,8,6}

for(i = 0; i < n; i++)
  for(j = 0; j < n; j++)
    if(i != j) resultArray[i] *= inputArray[j];

ただし、問題は、複雑さがO（n）
を超え てはならないことです。また、除算を使用することは許可されていません。
どうすればこれを解決できますか？

4

5 に答える 5

4

次のような DP アプローチを使用できます。

vector<int> products(const vector<int>& input) {
    int N = input.size();
    vector<int> partial(N+1); // partial[i] = input[0]...input[i-1]. partial[0] = 1
    partial[0] = 1;
    for (int i = 0; i < N; ++i) partial[i+1] = input[i]*partial[i];
    vector<int> ans(N);
    int current = 1;
    for (int i = N-1; i >= 0; --i) {
        // current is equal to input[i+1]...input[N-1]
        ans[i] = partial[i]*current;
        current *= input[i];
    }
    return ans;
}

このアプローチの考えられる使用法の 1 つは、割り切れないものを扱う場合です (たとえば、行列に関する同じ問題を考えてみてください)。

私は STL ベクトルを使用してこのソリューションを実行しましたが、もちろんコードは C 配列で動作するように簡単に「変換」できます。

于 2012-08-26T12:08:17.640 に答える
4

ネタバレしすぎないように、2 つの変数を使用して乗算の結果を格納するようにしてください。i 番目の要素の左側と i 番目の要素の右側にある乗算の累積結果の両方です。

于 2012-08-26T12:03:55.287 に答える
1

奇数による乗算は、乗算のみを使用して元に戻すことができることをご存知ですか? 「正確な分割」のようなものと呼ばれる Hacker's Delight を参照してください。そこで説明されているように、このトリックは偶数にも拡張できます。n 番目の数を 2 回の掛け算で「割る」ことができます。

于 2012-08-26T12:01:09.203 に答える
1 
main()
{

      int i,l,r,x[5]={1,2,3,4,5},y[5]; // x is the initial array, y is the final array

      int n = 5; // n be the size of the array, here already defined as 5

      l = 1; // l is the product of the values of the left side of an index in x
      r = 1; // r is the product of the values of the right side of an index in x

      for (i=0 ; i<5 ; i++) y[i]=1; // initialising all y values to 1

      for (i=0 ; i<5 ; i++)
      {
          y[i] = y[i]*l ;
          y[n-i-1] = y[n-i-1]*r;

          l = l*x[i];
          r = r*x[n-i-1];

      }

      for (i=0; i<5; i++) printf("%d\n",y[i]);

}
于 2012-08-26T13:10:06.750 に答える
0

Daniel Fleischman の回答を見て、彼には非常に多くのコード行があるため、独自の実装を提供する必要があると判断しました。

int i, buffer=1, result[n];
for(result[0]=1,i=1;i<n;i++) result[i] = result[i-1]*inputArray[i-1];
for(i=n-1,buffer=1;i>=0;buffer*=inputArray[i],i--) result[i]*=buffer;

3 行のコード (すべての脂肪を切り取ったもの)。

http://ideone.com/EaQiu

于 2012-08-26T12:26:44.770 に答える