时间戳

首页 > 解决方案 > 查找数组中乘积小于等于常数 k 的所有对

c++ - 查找数组中乘积小于等于常数 k 的所有对

问题描述

int fun(int A[], int n, int k) {
  int count = 0;
  int i = 0;
  int j = n - 1;
  
  // Traverse the array
  while (i < j) {
    if (A[i] * A[j] <= k) {
      count += (j - i);
      i++;
    }
    else {
      j--;
    }
  } 
  return count; 
}

我使用以下逻辑来解决问题：

  1. 我已经对数组进行了排序。
  2. 我使用了上面提到的两指针方法来查找乘积小于或等于 k ​​的对数。该过程的时间复杂度原来是 O(N log N) 请建议对我的过程进行任何优化，以便我得到这个问题的 O(n) 解决方案。我可以在不排序的情况下解决这个问题吗？

标签： c++algorithmsorting

解决方案

这与 2SUM 问题有关（并从 3SUM 问题解决方案中受益）。不存在完整的O(N)解决方案，因为可能有尽可能多的O(N)对。但是，如果对的数量是，O(N)那么我们可以解决它O(N)。

考虑一下a + b = k，我们可以将其重写为a - k = b。对于每个a我们可以b通过首先将所有数字存储在一个集合中并进行O(1)查找来检查是否存在。然后对于a我们计算的每一个b，我们可以验证 b 是否存在于 中O(1)，做那次N，我们就有了O(N)。

if 怎么样a * b <= k，现在我们使用k / b <= b. 这看起来很棘手，但实际上要容易得多。它引导我们使用O(N + Z)输出敏感算法。Z是有效对的数量。Z可以高达O(N^2).

让我们考虑一个例子。假设数字范围从10 to 1000，并且k是10000。a * b <= k. 使用重写的公式，我们得到10000 / b =< 10000/10 =< 1000 <= 10 <= b和10000 / 1000 <= 10 <= b。因此，任何小于1000的值都是潜在的有效解决方案（因为 10 也小于 1000）。这是因为我们现在可以通过过滤掉所有高于 70 的值来有效地绑定值。假设有M值。然后我们只需要对这些M值进行排序，这意味着它只需要O(M log M)排序。但是，O(M log M)可能比O(Z)实际使用的要少，所以我O(Z)改用了。虽然我想我们可以在技术上调用它O(N + M log M + Z)。这为我们提供了我们的输出敏感方法，N如果Z远低于 N ，则可以将其视为 O(·)。

  1. 找到数组的最小值，调用它M。O(N). 计算b，可能的解决方案的最大值，从这里。
  2. 获取查找所有小于或等于 的值的列表M。对列表进行排序。O(M log M)（M作为这个列表的列表）
  3. 遍历列表以找到有效的解决方案。基本上从最大值到最小值（b）和最小值到最大值（a）来限制解决方案。a * b > k如果我们运行 atO(Z)而不是 ，则停止内部循环O(M^2)。O(Z)

Python解决方案（不确定您需要什么，但即使您需要转换代码也应该有所帮助）：

# Step 1. Find b, O(N)
h = 10000.0 # Avoid integer division
values = [10, 100, 250, 300, 800, 10000]
m = min(values)
b = h / m

# Step 2. Bound, O(N)
bounded = []
for x in values:
  if x <= b:
    bounded.push(x)

# Step 3. List solutions, O(Z)
sorted_bounded = bounded.sorted()
reverse_bounded = bounded.sorted(reverse=true)
solutions = []
for i in range(len(reverse_bounded)):
  b = reverse_bounded[i]
  for j in range(len(sorted_bounded))
    a = sorted_bounded[j]
    if a * b <= k:
      solutions.push([a,b])
    else:
      break

其中一种可能可以在对使用数组两个方向的点更友好的语言中删除。

如果我们只需要找到解决方案的总数，我们可以在 O(N + M log M) 中运行它。因为我们可以对排序M列表进行二分查找，找到满足要求的最大值的索引。

我在这个例子中使用了正 * 正。如果您有负数，只需将 、 和 处理positive * positive为negative * negative可能negative * negative值的单独列表，a它将b数组O(N)拆分为正数和负数。更复杂，但肯定是可行的，只是不想在这个例子中去那里。

编辑1：刚刚注意到这是产品而不是添加。仍然有效，但需要更改+和*更新-示例/。

编辑2：已修复。

编辑 3：这是在添加语言之前发布的。不熟悉C++。

推荐阅读