返回a的总数(a,b),其中a来自A,b来自B,a + b是<= c

Question

试着做一些练习,我跑过这个问题......

给定两个int数组A和B,以及一个int c,返回对的总数(a,b),其中a来自A,b来自B,a + b是<= c

立即想出了蛮力解决方案,但似乎无法连接点以便在更好的时间复杂性中做到这一点.我首先尝试对数组进行排序,并尝试找到某种类型的模式,但这并没有让我任何地方.我想过一个数组有负数的情况.在这种情况下,我不能只查看A或B中的值并检查它本身是否小于c,因为在另一个数组中可能存在负值,当它们加在一起时会得到<= c的结果.任何见解,想法或线索将不胜感激.

import java.util.*;

public class CountPairs {

    public static void main(String args[]){
        int arrayA[] = {32,45,9,4};
        int arrayB[] = {43,457,54,90};

        Scanner scan = new Scanner(System.in);

        System.out.println("Choose the value that you want to find pairs <= ");
        int c = scan.nextInt();

        System.out.println("The total number of pairs are : " + pairs(arrayA, arrayB, c));
    }

    public static int pairs(int A[], int B[], int n) {
        int count = 0;

        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B.length; j++) {
                int total = A[i] + B[j];

                if(total <= n)
                    count++;
            }
        }

        return count;
    }
}

Answer 1

让我们花一点时间来了解使用Javaslang并使用声明性功能方法时任务变得多么容易:

初步数据:

int arrayA[] = {32, 45, 9, 4};
int arrayB[] = {43, 457, 54, 90};

int c = 100;

解:

int result = List.ofAll(arrayA)
  .crossProduct(List.ofAll(arrayB))
  .distinct()
  .count(t -> t._1 + t._2 <= c);

Answer 2

如果您是为了练习而这样做,那么我建议您完全忽略性能并且要求清晰的代码.

开发人员通常习惯于以简单和清晰为代价使代码尽可能高效,这通常是一个坏主意,因为几乎不可能提前告诉性能问题.

在清晰度方面,您可能需要考虑使用Stream API而不是常见的迭代:

Arrays.stream(arrayA)
    .flatMap(n1 -> Arrays.stream(arrayB).map(n2 -> n1 + n2))
    .filter(n -> n <= total)
    .count();

Answer 3

我们可以解决这个O(m log m + n log m) = O(log m (m + n))时间,其中m越小阵列的基数; n,更大.首先,对较小的数组进行排序:

A = {32,45,9,4};
B = {43,457,54,90};

=> A = {4,9,32,45}

现在对于每个bin B,使用二进制搜索A来查找最大值a小于或等于的索引(c - b).添加(index + 1)到累积结果.例如:

c = 100:
  43  => 100 - 43  = 57   => largest a <= c-b = 45, index 3 => add 4 to result
  457 => 100 - 457 = -357 => largest a <= c-b = None
  54  => 100 - 54  = 46   => largest a <= c-b = 45, index 3 => add 4 to result
  90  => 100 - 90  = 10   => largest a <= c-b = 9,  index 1 => add 2 to result

result = 4 + 4 + 2 = 10
 corresponding with the following pairs:
 (43,4),(43,9),(43,32),(43,45),(54,4),(54,9),(54,32),(54,45),(90,4),(9,9)