java – 在数组中搜索缺失的数字时的性能

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了java – 在数组中搜索缺失的数字时的性能，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1040字，纯文字阅读大概需要2分钟。

内容图文

给定是一个列表,其中包含1-20之间的所有2个数字(随机排序).
我需要找到那两个数字.

这是我提出的(工作)计划：

public static void main(String[] args) {
    int[] x= {1,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19};
    ArrayList al= new ArrayList();
    Map map= new HashMap();
    for(int i=0;i<x.length;i++)
    {
        map.put(x[i], x[i]);
    }
    for(int i=1;i<=20;i++)
    {
        if(map.get(i)==null)
            al.add(i);
    }
    for(int i=0;i<al.size();i++)
    {
        System.out.println(al.get(i));
    }
}

我想从性能的角度(内存和bigO(n))知道程序是否良好？

解决方法:

你不需要地图.只是一个大小为20的额外布尔数组.

for (int i = 0; i < input.length; i++)
   arr[input[i]] = true;

for (int i = 1; i <= 20; i++)
   if (arr[i] == false) {
      //number `i` is missing
   }     

现在我将展示一个简单的数学解决方案.

首先对数组中的所有数字求和.例如,对于1,2,3,4,5中的数字,您有5,1,4.因此缺少2和3.我们可以通过数学轻松找到它们.

5 + 1 + 4 = 10
1 + 2 + 3 + 4 + 5 = 15

所以我们知道x y = 15 – 10 = 5
现在我们将得到第二个等式：

1 * 4 * 5 = 20
1 * 2 * 3 * 4 * 5 = 120
=> x * y = 120 / 20 = 6

所以：

x + y = 5
x * y = 6

=&GT x = 2,y = 3或x = 3,y = 2,它们是相同的.

所以x = 2,y = 3

内容总结

以上是互联网集市为您收集整理的java – 在数组中搜索缺失的数字时的性能全部内容，希望文章能够帮你解决java – 在数组中搜索缺失的数字时的性能所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端