jjzjj

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

coder 2024-04-02 原文

我在面试中遇到了这个问题。 假设您有一个未排序的整数 数组，其可能值为正、负和零。您还有一个变量 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 我们可以在任何新的数据结构中存储最小数量的条目，但它应该是最小的，而不是该数据结构中原始元素或太多元素的完整副本

最佳答案

假设我们有:

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。这通常是面试的重点，谷歌喜欢它。 :)

关于java - 从数组中找到对(2 个元素)，其乘积必须大于给定的整数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49767236/

给定javacodestrongvaluesarraysalgorithm

有关java - 从数组中找到对(2 个元素)，其乘积必须大于给定的整数的更多相关文章

  1. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  2. ruby - 多次弹出/移动 ruby​​ 数组 - 2

    我的代码目前看起来像这样numbers=[1,2,3,4,5]defpop_threepop=[]3.times{pop有没有办法在一行中完成pop_three方法中的内容？我基本上想做类似numbers.slice(0,3)的事情，但要删除切片中的数组项。嗯...嗯，我想我刚刚意识到我可以试试slice! 最佳答案 是numbers.pop(3)或者numbers.shift(3)如果你想要另一边。 关于ruby-多次弹出/移动ruby​​数组，我们在StackOverflow上找到一

  3. ruby - 将数组的内容转换为 int - 2

    我需要读入一个包含数字列表的文件。此代码读取文件并将其放入二维数组中。现在我需要获取数组中所有数字的平均值，但我需要将数组的内容更改为int。有什么想法可以将to_i方法放在哪里吗？ClassTerraindefinitializefile_name@input=IO.readlines(file_name)#readinfile@size=@input[0].to_i@land=[@size]x=1whilex 最佳答案 只需将数组映射为整数:@land边注如果你想得到一条线的平均值，你可以这样做:values=@input[x]

  4. ruby - 通过 erb 模板输出 ruby​​ 数组 - 2

    我正在使用puppet为ruby​​程序提供一组常量。我需要提供一组主机名，我的程序将对其进行迭代。在我之前使用的bash脚本中，我只是将它作为一个puppet变量hosts=>"host1,host2"我将其提供给bash脚本作为HOSTS=显然这对ruby​​不太适用——我需要它的格式hosts=["host1","host2"]自从phosts和putsmy_array.inspect提供输出["host1","host2"]我希望使用其中之一。不幸的是，我终其一生都无法弄清楚如何让它发挥作用。我尝试了以下各项:我发现某处他们指出我需要在函数调用前放置“function_”……这

  5. ruby - 检查数组是否在增加 - 2

    这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife

  6. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/

  7. ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2

    我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat

  8. ruby - 在 Ruby 中用键盘诅咒数组浏览 - 2

    我正在尝试在Ruby中制作一个cli应用程序，它接受一个给定的数组，然后将其显示为一个列表，我可以使用箭头键浏览它。我觉得我已经在Ruby中看到一个库已经这样做了，但我记不起它的名字了。我正在尝试对soundcloud2000中的代码进行逆向工程做类似的事情，但他的代码与SoundcloudAPI的使用紧密耦合。我知道cursesgem，我正在考虑更抽象的东西。广告有没有人见过可以做到这一点的库或一些概念证明的Ruby代码可以做到这一点？ 最佳答案 我不知道这是否是您正在寻找的，但也许您可以使用我的想法。由于我没有关于您要完成的工作

  9. ruby - 如何在 Grape 中定义哈希数组？ - 2

    我使用Ember作为我的前端和GrapeAPI来为我的API提供服务。前端发送类似:{"service"=>{"name"=>"Name","duration"=>"30","user"=>nil,"organization"=>"org","category"=>nil,"description"=>"description","disabled"=>true,"color"=>nil,"availabilities"=>[{"day"=>"Saturday","enabled"=>false,"timeSlots"=>[{"startAt"=>"09:00AM","endAt"=>

  10. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

随机推荐