我想知道是否有可能以小于O(N^2)的速度解決這個問題。 有一個長度為N的陣列a和除數k。需要計算所有可能的對(a[i], a[j])，如i < j和a[i] a[j]能被k無余地除以。 我所得到的是兩個嵌套回圈。 我可以用a[i]除以k的所有余數來創建陣列，但接下來需要在這個陣列中做類似的嵌套回圈，而且又是O(N^2)。
uj5u.com熱心網友回復：
在a[i]mod k上對陣列進行排序，這可以在O(N Log N)的時間內完成。
用兩個索引掃描陣列，從左到右和從右到左，以這樣的方式檢測元素的序列，使其總和mod k為0，并將這些序列的長度相乘。這可以在O(N)時間內完成。
例如，k=5
2, 9, 21, 13, 1, 8, 22, 6
排序后，
1, 21, 6, 22, 2, 13, 8, 9
1 1 1 2 2 3 3 4
而序列是
||1, 21, 6|2, 22|13, 8|9|。
||1 1 1|2 2| 3 3|4|
即3x1 2x2對。
你需要一些額外的技巧來避免計算i≥j的對。例如，你可以給每個元素加上它在陣列中的初始索引，然后按字母順序對值mod k和索引進行排序。然后在計算配對時，通過一種合并程序，你可以列舉出有效的配對。總的復雜度仍然是O(N)。
2, 9, 21, 13, 1, 8, 22, 6
0 1 2 3 4 5 6 7
排序之后，
21, 1, 6, 2, 22, 13, 8, 9
1 1 1 2 2 3 3 4
2 4 7 0 6 3 5 1
而序列是
||21, 1, 6|2, 22|13, 8|9|。
|| 1 1 1|2 2| 3 3|4|
|| 2 4 7|0 6| 3 5|1|
現在從|2, 22|13, 8|算起，我們看到2后面是13, 8，22后面沒有，因此有2 0個有效對。
uj5u.com熱心網友回復：
我們可以用一個哈希圖在O(n)中解決這個問題，其中鍵是余數，值是我們在迭代時看到這個余數的次數。對于每一個數字，在第一個被插入后，在元素A[i]被插入前，如果它存在于地圖中，則在結果中加入鍵的值，k-(A[i]mod k)。然后將鍵值A[i]mod k的計數遞增1。
uj5u.com熱心網友回復：
創建一個從0到k-1的余數桶。現在用除數k除掉陣列中的每個數字，并根據除以k后產生的余數將數字放入余數桶。現在像這樣創建一對 -
每個產生余數1的數字都可以與所有產生余數k - 1的數字組成一對，因為它們的總和將完全被k所除（沒有余數）。
同樣，在余數2桶中的數字將與余數k - 2桶中的數字組成一對。對i<=j這樣做。
另外，在余數0桶中的所有數字將在它們之間形成一對。
時間復雜度是O(n)，空間復雜度是O(k)（對于余數桶）。
編輯：
如果只需要計算對的數量，那么余數桶可以像一個簡單的陣列（其所有元素初始化為0），每個元素，在一個特定的索引，將包含陣列的元素數量，產生相當于該索引的余數。做簡單的計算--余數桶索引的數字1乘以余數桶索引的數字k-1，索引的數字2乘以索引的數字k-2，以此類推（i<=j）。另外，計算一下索引0處的數字的可能配對。將它們全部加起來，這就得到了答案。
uj5u.com熱心網友回復：
寫一個遞回函式，然后你會看到有重疊的結果（你又在做同樣的計算）。然后將該程式轉化為動態編程模型，該模型將保存給定子陣列的結果。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/308798.html
標籤：
下一篇：我如何為每個類別挑選最低成本值？