java - 从数组中找到对(2 个元素)，其乘积必须大于给定的整数

Question

我在面试中遇到了这个问题。假设您有一个未排序的整数 数组，其可能值为正、负和零。您还有一个变量 k它持有一个整数。现在找到一对或多对，非重复的，如果存在，其乘积大于k . k可以是任何东西，+ve、-ve 或零

约束:您不能操作数组，这意味着任何排序或复制原始数组然后排序或更改值都受到限制。

如果可能，它应该低于 O(n^2)时间复杂度和最小空间(没有明确提到空间，但他们说使用尽可能低的空间)

例如:给定Array [0,-1, 5, 45, 4, 1, -3]和 k = 20我的解决方案在面试中给出:

我的解决方案:第一个是蛮力使用 O(N^2)并尝试为该对获取产品并进行检查。现在我即兴创作了以下逻辑

假设 k = 40 , 我得到了 array[i] = 2 .现在int divide = k/array[i] . divide+ = 1 .如果我遇到任何数字，请说 array[j] > divide , 和 array[j] < k , 然后是 int product = array[i] * array[j] 的乘积将是 product > k .

逻辑:如果我有一个数字 1000 并且我得到了 array[i] = 3对于 i 的某些值.如果我得到 n = 1000 / array[i]并递增 n = n+1 , 如果 n存在于数组中然后是 n * array[i] > 1000 的乘积

编辑:+ve 表示正，-ve 表示负，找到所有对而不是在第一对处停止。 EDIT 2 我们可以在任何新的数据结构中存储最小数量的条目，但它应该是最小的，而不是该数据结构中原始元素或太多元素的完整副本

Answer 1

假设我们有:

int[] values;
int k;
// Found pairs will be fed to this consumer
BiConsumer<Integer, Integer> results;

天真的暴力实现是O(n^2)。问题是，是否有可能让它变得更好。我个人不这么认为。在最坏的情况下，数组的所有元素都可能成对。例如，如果数组包含不同的正整数且 k=0。即使您对数组进行排序，您仍然需要实际生成对。这意味着蛮力实际上已经足够好了。

现在是空间复杂度。问题是您需要生成非重复 对。因此，您需要跟踪哪些对已经看过，哪些没有。天真地说这是 O(n^2) 但我认为这可以减少到 O(n)。

下面是代码草图:

Set<Integer> seenNumbers = new HashSet<>();
for (int i = 0; i < values.length - 1; i++) {
    int left = values[i];

    if (seenNumbers.contains(right)) {
        continue;
    }

    for (int j = i + 1; j < values.length; j++) {
        int right = values[j];

        if (seenNumbers.contains(right)) {
            continue;
        }

        if (((long)left*(long)right) > k) {
            results.accept(left, right);
            if (left != right) {
                results.accept(right, left);
            }
        }
    }
    seenNumbers.add(left);
}

此代码为 seenNumbers 使用了 O(n) 的额外空间。我认为只跟踪已经遇到的数字就足够了。如果我们再次遇到某个数字，这意味着它已经被处理为values[i]，这意味着已经生成了具有该数字的所有可能对。

我再次考虑了您建议的“划分”解决方案。因为这很棘手。您不能只使用 k/values[i] + 1 并将其用作右侧的最小值。您需要考虑 values[i]==0 以及负值 values[i]。并不是说它不可能，而是它非常麻烦并且非常容易出错。我可能会在采访中提到这一点，但宁愿不这样做。简单的乘法要容易得多。

但即使是简单的乘法，您也必须考虑整数溢出。因此 (long)left*(long)right。这通常是面试的重点，谷歌喜欢它。 :)