試圖用這個來加快演算法開發：
You are given an array of integers a and an integer k. Your task is to calculate the number of ways to pick two different indices i < j, such that a[i] a[j] is divisible by k.
Example
For a = [1, 2, 3, 4, 5] and k = 3, the output should be solution(a, k) = 4.
這是我的java解決方案：
long solution(int[] a, int k) {
final BiPredicate<Integer, Integer> isDivisible = (x,y) -> (a[x] a[y]) % k == 0;
long counter = 0;
for(int i = 0; i < a.length - 1; i ) {
for(int j = i 1; j < a.length; j ){
if(isDivisible.test(i,j)) {
counter ;
}
}
}
return counter;
}
它通過了所有測驗，期望性能測驗，必須有一些更多的性能解決方案，有什么想法嗎？
uj5u.com熱心網友回復：
您的方法是一種蠻力解決方案，并且具有二次時間復雜度。
這是一個改進：
考慮兩個數字的和是k的倍數，當
- 它們都是k的倍數，或者
- 余數除以k時的總和為k。
如果我們可以計算每個可能的余數有多少個數，我們就可以找到互補余數的個數，然后取乘積。最后，我們需要將這個總數減半，因為我們還計算了i > j. 余數為 0 或 的一半的情況k需要特別注意，因為該產品將包含 的情況i == j，因此需要丟棄這些情況。
這是一個實作：
long solution(int[] a, int k) {
final HashMap<Integer, Integer> count = new HashMap<>();
for (int i = 0; i < a.length; i ) {
int key = a[i] % k;
count.put(key, count.getOrDefault(key, 0) 1);
}
int counter = 0;
for (Map.Entry<Integer, Integer> set : count.entrySet()) {
int mod = set.getKey();
int freq = set.getValue();
counter = freq * (mod > 0 && k != 2*mod
? count.getOrDefault(k - mod, 0)
: freq - 1);
}
return counter / 2;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/415941.html
標籤：