返回对（a， b）的总数，其中 a 来自 A，b 来自 B，a + b < = c

algorithm java

2022-09-03 12:13:54

试图做一些练习，我遇到了这个问题...

给定两个 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;
    }
}

答案 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);

答案 2

我们可以及时解决这个问题，其中较小数组的基数;，则较大。首先，对较小的数组进行排序：O(m log m + n log m) = O(log m (m + n))mn

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

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

现在，对于中的每个，使用二进制搜索 on 来查找最大小于或等于的索引。添加到累积结果中。例如：bBAa(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)

返回对 （a， b） 的总数，其中 a 来自 A，b 来自 B，a + b < = c

返回对（a， b）的总数，其中 a 来自 A，b 来自 B，a + b < = c