(A卷,100分)- 二元组个数（Java & JS & Python）

题目描述

给定两个数组a，b，若a[i] == b[j] 则称 [i, j] 为一个二元组，求在给定的两个数组中，二元组的个数。

输入描述

第一行输入 m
第二行输入m个数，表示第一个数组

第三行输入 n
第四行输入n个数，表示第二个数组

输出描述

二元组个数。

用例

题目解析

很简单的双重for，

/**
 *
 * @param {Array} arrM 第二行输入的数组
 * @param {Number} m 第一行输入的数字m
 * @param {Array} arrN 第四行输入的数组
 * @param {Number} n 第二行输入的数字n
 * @returns
 */
function getResult(arrM, m, arrN, n) {
  let count = 0;

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (arrM[i] === arrN[j]) {
        count++;
      }
    }
  }

  return count;
}

但是不知道数量级多少，如果数量级比较大的话，则O(n*m)可能罩不住。

因此，我们还需要考虑下大数量级的情况。

我的思路如下：

先找找出m数组中，在n数组中出现的数及个数，在找出n数组中，在m数组中出现的数及个数，比如：

用例2中

countM = {2:2, 4:1}

countN = {2:2, 4:1}

然后将相同数的个数相乘，最后求和即为题解，比如2*2 + 1*1 = 5

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 4) {
    const m = lines[0] - 0;
    const arrM = lines[1].split(" ").map(Number);

    const n = lines[2] - 0;
    const arrN = lines[3].split(" ").map(Number);

    console.log(getResult(arrM, m, arrN, n));

    lines.length = 0;
  }
});

function getResult(arrM, m, arrN, n) {
  const setM = new Set(arrM);
  const setN = new Set(arrN);

  const countM = {};
  for (let m of arrM) {
    if (setN.has(m)) countM[m] ? countM[m]++ : (countM[m] = 1);
  }

  const countN = {};
  for (let n of arrN) {
    if (setM.has(n)) countN[n] ? countN[n]++ : (countN[n] = 1);
  }

  let count = 0;
  for (let k in countM) {
    count += countM[k] * countN[k];
  }

  return count;
}

Java算法源码

import java.util.*;
import java.util.stream.Collectors;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int m = Integer.parseInt(sc.nextLine());
    List<Integer> listM =
        Arrays.stream(sc.nextLine().split(" ")).map(Integer::parseInt).collect(Collectors.toList());

    int n = Integer.parseInt(sc.nextLine());
    List<Integer> listN =
        Arrays.stream(sc.nextLine().split(" ")).map(Integer::parseInt).collect(Collectors.toList());

    System.out.println(getResult(listM, listN));
  }

  public static int getResult(List<Integer> listM, List<Integer> listN) {
    HashSet<Integer> setM = new HashSet<Integer>(listM);
    HashSet<Integer> setN = new HashSet<Integer>(listN);

    HashMap<Integer, Integer> countM = new HashMap<>();
    for (Integer m : listM) {
      if (setN.contains(m)) {
        countM.put(m, countM.getOrDefault(m, 0) + 1);
      }
    }

    HashMap<Integer, Integer> countN = new HashMap<>();
    for (Integer n : listN) {
      if (setM.contains(n)) {
        countN.put(n, countN.getOrDefault(n, 0) + 1);
      }
    }

    int count = 0;
    for (Integer k : countM.keySet()) {
      count += countM.get(k) * countN.get(k);
    }

    return count;
  }
}

Python算法源码

# 输入获取
m = int(input())
arrM = list(map(int, input().split()))

n = int(input())
arrN = list(map(int, input().split()))


# 算法入口
def getResult(arrM, arrN):
    setM = set(arrM)
    setN = set(arrN)

    countM = {}
    for m in arrM:
        if m in setN:
            if countM.get(m) is None:
                countM[m] = 1
            else:
                countM[m] += 1

    countN = {}
    for n in arrN:
        if n in setM:
            if countN.get(n) is None:
                countN[n] = 1
            else:
                countN[n] += 1

    count = 0
    for k in countM.keys():
        count += countM[k] * countN[k]

    return count


# 算法调用
print(getResult(arrM, arrN))