PHPでハミング距離の合計を計算する方法

2 つの整数のハミング距離は、2 つの数値の異なるバイナリ対応ビットの数を指します。今回は、PHP でハミング距離の総和を計算する方法を編集者が紹介しますので、必要な場合は参考にしてください。

2 つの整数のハミング距離は、これら 2 つの数値の 2 進数の異なる対応するビットの数を指します。

配列内の任意の 2 つの数値間のハミング距離の合計を計算します。

例:

输入: 4, 14, 2
输出: 6
解释: 在二进制表示中，4表示为0100，14表示为1110，2表示为0010。（这样表示是为了体现后四位之间关系）
所以答案为：HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

注:

配列内の要素の範囲は 0 ～ 10^9 です。配列の長さは 10^4 を超えることはできません。

問題解決のアイデア 1

ペアごとの組み合わせの数を列挙し、ハミング距離を累積するこれが最も単純で直接的な解決策です。

結果として、データ量が多く、階乗の数が多すぎる場合にはタイムアウトになります。

コード

class Solution {
    /** 
    * @param Integer[] $nums 
    * @return Integer 
    */
    function totalHammingDistance($nums) {
        $count = count($nums);
        $sum = 0;
        for ($i = 0; $i < $count - 1; $i++) {
            for ($j = $i+1; $j < $count; $j++) 
            {
                $sum += $this->hm($nums[$i], $nums[$j]);
            }
        }
        return $sum;
    }
    // 汉明距离方法
    function hm($x, $y)
    {
        return substr_count(decbin($x ^ $y), &#39;1&#39;);
    }}

問題解決のアイデア 2 - 垂直方向の計算

私たちはよく次のように問題を分析します: 最も単純なケース -> 一般 、複雑な状況。以前は、考えられるすべてのペアごとの組み合わせを調べていました。

次に、別の角度から見てみましょう。int に 1 ビットしかない場合 -> int には 32 ビットがあります。

まず、int が 1 ビットしかない場合、つまり、配列 nums の要素が 0 か 1 の 2 つの状況しかない場合、このとき、ハミング距離の合計を求める手順は次のようになります。

まず、配列を 2 つのグループに分割し、1 つのグループはすべて 0 桁で、もう 1 つのグループはすべて 1 桁で、2 つの数値グループをペアにして結合し、1 つを a として記録し、もう 1 つを b として記録します。 a と b が両方とも 0 のグループに由来する場合、または両方とも 1 のグループに由来する場合、ハミング距離は生成されません。ただし、a と b の一方が 0 グループに属し、もう一方が 1 グループに属している場合、ハミング距離が生成されます (nums 配列の要素数を n、0 の要素数を k とする) 、次に 1 の要素の数です。数値は n-k です。その場合、前のステップで生成できるハミング距離の合計は k*(n-k)k*(n-k) になります。これは、int が 1 しかない場合のハミング距離の合計です。 digit.

int の桁数が 1 ビットから 32 ビットに拡張されている場合、各ビットが走査され、このビットでのハミング距離の合計が求められ、一緒に累積されます。 $O(N^2)$ から $O(32\times N)$ までのアルゴリズムの複雑さは $O(N)$ です。

次の例を見てください:

十进制       二进制
4:        0 1 0 0
14:        1 1 1 0
2:        0 0 1 0
1:        0 0 0 1

最初に最後の列を見てください。3 つの 0 と 1 つの 1 があります。すると、それらの間のハミング距離は 3、つまり 1 と 1 になります。残りの 3 つの 0。それぞれの距離が累積され、3 番目の列を見ると、累積されたハミング距離は 4 になります。これは、各 1 から 2 つの 0 を含む 2 つのハミング距離が生成されるためです。同様に、2 番目の列も 4 で、最初の列は 3 です。各列のペアごとの組み合わせのハミング距離の合計は、各列の 0 の数と 1 の数の合計です。各列のハミング距離の合計を合計すると、次の 2 つの要素間の距離になります。質問で必要な配列番号 ハミング距離の合計。

コード

class Solution {

    /** 
    * @param Integer[] $nums 
    * @return Integer 
    */
    function totalHammingDistance($nums) {
        $count = count($nums);
        $sum = 0;
        for($i = 0; $i < 32; $i++)
        {
            $tmpCount = 0; 
            
            for($j = 0; $j < $count; $j++)
            {
                $tmpCount += ($nums[$j] >> $i) & 1;
            }
            
            $sum += $tmpCount * ($count - $tmpCount);
        }
         
        return $sum;
    }
}

推奨学習: phpビデオチュートリアル

以上がPHPでハミング距離の合計を計算する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。