计算列表中产生可被 60 整除的总和的元素对的数量 - 降低时间复杂度 - java - SO中文参考

1
投票

错误解释

这段代码是正确的，但是测试软件由于“超时”而导致一些隐藏的测试用例失败，其中nums列表为10000，这意味着花费的时间太长。

我不会说代码是正确的（因为其中存在缺陷），而是你没有机会看到它在小输入上失败。

在内部

for

 循环中，您将索引

j

 的起始值初始化为

i

int j = i

。这意味着在内循环的第一次迭代中，您将一个元素添加到

本身： nums.get(i) + nums.get(j)

，然后检查它是否可以被

60

整除。

这可能会导致无效结果。内循环应以

j = i + 1

 开头。通过此修复，您将获得正确的暴力解决方案。

第二期-

术语.

你的代码计算的是

not Permutations, but Combinations 元素对（这不是学术上的吹毛求疵，结果会有所不同）。

作为一个简单的说明，假设输入是

[1,2,3]

，我们需要可被

3

整除的元素对的组合。只有一种组合：

[1,2]

，但有两种排列：

[1,2]

和

[2,1]

。

因为在你的暴力解决方案中

i < j

始终成立，它无法生成排列（因为它不会重新访问内部循环中的相同索引，所以只能考虑

[i,j]

，而不是

[j,i]

），它产生组合的数量。

现在，当问题陈述澄清后：

“找到可被给定数字整除的组合对的数量”，让我们开始实际的解决方案。

解决方案

正如

@Joachim Sauer 在评论中指出的那样，解决此问题的第一步是创建数组元素的频率数组% 60

（就像计数排序算法的第一阶段一样）。

那么我们有两种情况：

当考虑并集
60
```
中除以
```
[1,29]∪[31,59]
```
的余数时，我们需要计算相应余数频率的
```
笛卡尔积并将其添加到总数中。 IE。 frequency(1)xfrequency(59)
```
，
```
frequency(2)xfrequency(58)
```
，...一直到
```
frequency(29)xfrequency(31)
```
。 
```
注意，我们不应该碰frequency(0)
```
和
```
frequency(30)
```
（它们需要分开对待），我们不应该重复计算乘积，即我们不应该考虑像
```
frequency(59)xfrequency(1)
```
这样的反向组合。
```

组合

frequency(0)

和

frequency(30)

 是一种特殊情况，因为我们只能将它们与它们自身组合。对于这两种情况，我们都需要根据以下公式计算

二项式系数：

其中

n

 是频率数（对于

0

 或对于

30

），

k

 是组合中元素的数量，它始终等于

2

。

这就是实现的样子（

为了简化测试，除数60

不是硬编码的，而是作为方法参数提供的

）：

public static long getPairCount(List<Integer> list, int divisor) {
    int[] freq = new int[divisor]; // frequencies of modulus of array elements
    for (int next : list) freq[next % divisor]++;
    
    long count = 0;
    for (int left = 1, right = divisor - 1; left < divisor / 2 + divisor % 2; left++, right--) {
        count += ((long) freq[left]) * freq[right]; // a cartesian product gives a number of ways to form a pair
    }
    // Special cases: remainder 0 and remainder divisor / 2 - now with dialing with pure Combinations
    // and instead Cartesian product a Binomial coefficient needs to be calculated
    if (freq[0] > 1) count += binomialCoefficient(freq[0], 2 );
    if (divisor % 2 == 0 && freq[divisor / 2] > 1) count += binomialCoefficient(divisor / 2, 2 ); // should be only considered if divisor is
    return count;
}

public static long binomialCoefficient(int n, int k) {
    
    return factorial(n) / (k * factorial(n - k));
}

public static long factorial(int num) {
    long result = 1;
    for (int i = 1; i <= num; i++) result *= i;
    return result;
}

main()

public static void main(String[] args) {
    System.out.println(getPairCount(List.of(1, 2, 3), 3)); // [1, 2]
    System.out.println(getPairCount(List.of(1, 2, 3, 1, 2, 3, 4, 5), 7)); // [2, 5] x 2, [3, 4] x 2
    System.out.println(getPairCount(List.of(1, 2, 3, 1, 2, 3, 4, 5), 5)); // [2, 3] x 4, [1, 4] x 2
    System.out.println(getPairCount(List.of(1, 2, 3, 1, 2, 3, 4, 5, 5), 5)); // [2, 3] x 4, [1, 4] x 2, [5, 5]
}

输出：

1   // [1, 2]
4   // [2, 5] x 2, [3, 4] x 2
6   // [2, 3] x 4, [1, 4] x 2
7   // [2, 3] x 4, [1, 4] x 2, [5, 5]

0
投票

问题是要求降低时间复杂度。可能是时间复杂度为 O(n) 而不是 n 平方的解决方案。我在最近的一次面试中确实遇到过这个问题，但未能按时完成。离线解决了解决方案，如下所示。

import java.util.*;
class HelloWorld {
    public static void main(String[] args) {
        List<Integer> numbers = List.of(10,20,-30,10,40,30,10,0);
        
        System.out.println(checkSum(numbers, 30));
    }
    public static int checkSum(List<Integer> numbers, int targetMultiple) {

       /*The Map contains the num already seen in the list along 
       with how many times it was seen
       if targetMultiple is non 0 then we save the reminder instead of 
       num along with count seen.*/
       Map<Integer,Integer> diffMap = new HashMap<>();

        // sign does not matter as we are checking for multiples
        targetMultiple = Math.abs(targetMultiple);

        int total = 0;

        for (int num : numbers) {
            //if target multiple is 0, then we need to check if the negative of 
            //the given number is there in the list so the sum is 0.
            if (targetMultiple == 0) {
                // check existence of possible sum satisfying the required condition
                int diff = num != 0? -num : 0;
                Integer diffCount = diffMap.get(diff);
                if (diffCount != null) {
                    total += diffCount;
                } 

                //store the current number
                Integer numCount = diffMap.get(num);
                if (numCount != null) {
                   diffMap.put(num, numCount + 1); 
                } else{
                   diffMap.put(num, 1); 
                } 
                
            } else {
                int remainder = num % targetMultiple;
                int diff = targetMultiple - remainder;

               // check existence of possible sum satisfying the required condition

               // sum adding up to 0 is also a multiple 
               Integer negRemainderCount = diffMap.get(-remainder);
               if (negRemainderCount != null ) {
                    total += negRemainderCount;
               } 

               // sum adding to target multiple
                Integer diffCount = diffMap.get(diff);
                if (diffCount != null ) {
                    total += diffCount;
                }

               // store current remainder in map
                Integer remainderCount = diffMap.get(remainder);
                if (remainderCount != null) {
                   diffMap.put(remainder, remainderCount + 1); 
                } else {
                   diffMap.put(remainder, 1);  
                }
            }
        }
        return total;
        
    }
}

-1
投票

获取此代码

 public static int getPairs(List<Integer> nums, int divisor) {
    int result = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (i == divisor) {
          result++;
        } else {
          int j = 60 - i;
          if (nums.contains(j)) {
            result++;
          }
        }
    }
    return result;
  }

计算列表中产生可被 60 整除的总和的元素对的数量 - 降低时间复杂度

问题描述投票：0回答：3

3个回答

最新问题

计算列表中产生可被 60 整除的总和的元素对的数量 - 降低时间复杂度

问题描述 投票：0回答：3

3个回答

最新问题

问题描述投票：0回答：3