jjzjj

java - O(n) 算法在从 1 到 n(不是奇数)的连续整数数组中找到奇数输出

coder 2023-08-31 原文

我在试图弄清楚这个问题时遇到了很多麻烦，而这个问题的根源是创建一个 O(n) 的算法。复杂。这是我正在努力解决的问题:

An Array A of length n contains integers from the range [0, .., n - 1]. However, it only contains n - 1 distinct numbers. So one of the numbers is missing and another number is duplicated. Write a Java method that takes A as an input argument and returns the missing number; the method should run in O(n).

For example, when A = [0, 2, 1, 2, 4], oddOneOut() should return 3; when A = [3, 0, 0, 4, 2, 1], oddOneOut() should return 5.

显然这是一个很容易用 O(n<sup>2</sup>) 解决的问题算法，(很可能是 O(n) ，我只是没有看到它!)。我试图用各种方法解决它，但无济于事。我正在尝试用 Java 解决它，但如果您更习惯用 Python 解决它，那也很好。

提前致谢...

最佳答案

假设缺少的数字是x重复的是y .如果将所有数字相加，总和将为:

(n - 1) * n / 2 - x + y

从上面可以找到(x - y) .....(1)

同样，对数字的平方求和。总和将是:

(n - 1) * n * (2 * n - 1) / 6 - x<sup>2</sup> + y<sup>2</sup>

从上面你得到(x<sup>2</sup> - y<sup>2</sup>) ....(2)

(2) / (1) gives (x + y).....(3)

(1) + (3) 给出 2 * x这样你就可以找到x和 y .

请注意，在此解决方案中有 O(1)额外的存储空间并且是 O(n)时间复杂度。上面的其他解决方案是不必要的O(n)额外的存储空间。

混合 C/C++ 中的代码更清晰:

#include <stdio.h>

int findDup(int *arr, int n, int& dup, int& missing)
{
    int sum = 0;
    int squares = 0;

    for (int i = 0; i < n; i++) {
        sum += arr[i];
        squares += arr[i] * arr[i];
    }

    sum = (n - 1) * n / 2 - sum; // x - y

    squares = (n - 1) * n * (2 * (n - 1) + 1) / 6 - squares; // x^2 - y^2

    if (sum == 0) {
        // no duplicates
        missing = dup = 0;
        return -1;
    }
    missing = (squares / sum + sum) / 2; // ((x^2 - y^2) / (x - y) + (x - y)) / 2 = ((x + y) + (x - y)) / 2 = x

    dup = missing - sum; // x - (x - y) = y

    return 0;
}


int main(int argc, char *argv[])
{
    int dup = 0;
    int missing = 0;

    int a[] = {0, 2, 1, 2, 4};

    findDup(a, sizeof(a) / sizeof(int), dup, missing);
    printf("dup = [%d], missing = [%d]\n", dup, missing);

    int b[] = {3, 0, 0, 4, 2, 1};
    findDup(b, sizeof(b) / sizeof(int), dup, missing);
    printf("dup = [%d], missing = [%d]\n", dup, missing);

    return 0;
}

输出:

dup = [2], missing = [3]
dup = [0], missing = [5]

一些python代码:

def finddup(lst):
    sum = 0
    sumsq = 0
    missing = 0
    dup = 0
    for item in lst:
        sum = sum + item
        sumsq = sumsq + item * item
    n = len(a)
    sum = (n - 1) * n / 2 - sum
    sumsq = (n - 1) * n * (2 * (n - 1) + 1) / 6 - sumsq
    if sum == 0:
        return [-1, missing, dup]
    missing = ((sumsq / sum) + sum) / 2
    dup = missing - sum
    return [0, missing, dup]

found, missing, dup = finddup([0, 2, 1, 2, 4])
if found != -1:
    print "dup = " + str(dup) + " missing = " + str(missing)

print finddup([3, 0, 0, 4, 2, 1])

输出:

dup = 2 missing = 3
[-1, 0, 0]

关于java - O(n) 算法在从 1 到 n(不是奇数)的连续整数数组中找到奇数输出，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19370236/

java奇数codemissingduparraysalgorithmtime-complexitybig-o

有关java - O(n) 算法在从 1 到 n(不是奇数)的连续整数数组中找到奇数输出的更多相关文章

  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

随机推荐