time-complexity - 给定 2 个数组的分数总和 - O(n)？

Question

给你 2 个 int 数组。

                    A=[1,   2,   1]
                    B=[2,   3,   3]

    so fractions are: 1/2, 2/3,  1/3

A是分子，B是分母。所以分数是：1/2、2/3、1/3

找出总和为 1 的所有对。

示例：这里我们有 2/3 + 1/3 = 1，所以 count = 1

返回 1

返回模 10^9 +7，因为输入可能很大

我在 O(n^2) 中完成了一次，然后计算 2 的加法并检查它是否为 1 并更新计数器。

O(n) 有可能吗？

任何语言 idm 示例：

  function solution(integer array A, integer array B){
    return integer_counter;
  }

标签： time-complexitycomplexity-theory

Answer 1

这是使用 Dictionary 的 C# 解决方案

public static int SumOfFraction(int[] numerator, int[] denominator) {
  int count = 0;
  Dictionary < int, List < int >> keyValuePairs = new Dictionary < int, List < int >> ();

  for (int i = 0; i < denominator.Length; i++) {
    if (keyValuePairs.ContainsKey(denominator[i])) {
      keyValuePairs[denominator[i]].Add(numerator[i]);
    } else {
      keyValuePairs.Add(denominator[i], new List < int > {
        numerator[i]
      });
    }
  }

  foreach(var keypair in keyValuePairs) {
    if (keypair.Key == keypair.Value.Sum()) {
      count++;
    }
  }

  return count;
}