お互いの距離が数値の倍数である点の部分集合を見つける

Question

問題：線上の点を表す配列Aが与えられている。 [5,-4,1,3,6]、および番号M=3の場合、A内の点の最大部分集合がお互いの間の距離がMの倍数であることが分かります。

この例では、2つの可能なサブセットは[-4,5]（距離9）と[3,6]（距離3）になります。

明白なブルートフォースの解決策は、O(N^2)時間内の各点のペア間の距離を計算し、サブセットを段階的に構築することによって候補の集合を構築することです。

もっと効率的なソリューションはありますか？

Answer 1

配列内の数字を繰り返し、それぞれのモジュラスMを計算し、結果でグループ化します。最大のグループは最大のサブセットです。

[5,-4,1,3,6]はあなたが負の数を処理する方法世話をする必要があると思います[2,2,1,0,0]

を与えるだろう、ネガのための剰余演算が他の人に（例えばPHP）differently in some languagesに定義されていますが、MODたい（-4、3）を評価します2、-1ではなく。 （M - （-x mod M））mod M

数値を含むリストのハッシュマップをモジュラスで保存することで、数値を効率的にグループ化することができます。