シーケンス内の正方形の数字

共通の差異を持つ配列内の正の整数シーケンス2 たとえば2 4 6 8 ここで、各数字をその正方形で置き換えます。計算を効率的に実行します。私はこの質問をインタビューで尋ねられ、2の倍数の演算であるためビット演算子を使って彼にo（n）解を与えました。より良い方法があればお勧めします。シーケンス内の正方形の数字

出典

2011-01-19 algo-geeks

「各数字を四角で置き換えてください」という意味を明確にすることはできますか？配列のすべての要素を少なくとも1回訪問して更新する必要があるので、これはΩ（n）時間かかる必要があります。具体的に最適化しようとしているのは何ですか？ – templatetypedef

@aboveええ私がやったのと同じアプローチ。私はちょうどビット賢明な演算子でそれをやっているよりも数字を正方形にする方法があることを知りたかった。 –

Ummmmm ...私はあなたのスクエアリングアルゴリズムを取得するか分からない。あなたはそれを説明しようと思いますか？具体的にどのようにビットごとの操作を使用する？ –

いいですが再帰的です。 :-)

(n+2)(n+2) = n**2 + 4*n + 4 // and you got n**2

出典

2011-01-19 07:14:55 Anycorn

@Chrisが修正されました – Anycorn

@aaa：ごめんなさい、私のコメントを削除しました。ただ編集するつもりでした:) –

+1 - これは面接官が得ていたものだと思います。しかし、私は、これを利用するプログラムが単純な乗算を使うプログラムよりも高速になるとは思っていません。数値がプリミティブ型の整数型を使って表現されていると仮定します。 IMO、これはかなり不自由な質問です。「巧妙な」回答を提供する人を除外することが目的でない限り。 –

class Square 
{ 
    public static int[] sequence(int[] array) 
    { 
    int[] result=new int[array.length]; 
    for(int i=0;i<array.length;i++) 
    { 
     result[i]=array[i]*array[i]; 
    } 
    return result; 
    } 
} 

// test cases: 
// Square.sequence(new int[]{2,4,6,8}) 
//out put->{ 4, 16, 36, 64 }

出典

2011-01-19 07:09:33 kamla

あなたのアプラックを詳しく説明してください。 –

本当にインタビュアーに依存していて、彼らが「正しいこと」と思っています。それが私だったら、（n < < 2）+ 4がきちんとしていたと思っていたのですが、反対に私は自分のコードでそれを見るのは嫌です。メンテナンスにはもっと多くの考えが必要です。良いオプティマイザがまったくいい仕事をする可能性もあります。

私は、「効率的な操作を実行する」というフレーズは、インタビュアーが速い計算を求めていた可能性が高いと考えています。それはまだO（n）ですが、2つのO（n）アルゴリズムを比較するとき、係数が再び重要になることを忘れないようにしてください。

出典

2011-01-19 07:39:12

シーケンス内の正方形の数字

答えて

関連する問題