在数组中搜索缺失数字时的性能 [英] Performance when searching for missing numbers in array

问题描述

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

Given is a list containing all but 2 numbers between 1-20 (randomly ordered). I need to find those 2 numbers.

这是我想出的(工作)程序:

This is the (working) program I came up with:

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))这个程序是否好?

I would like to know if the program is good from a performance point of view (memory and bigO(n))?

推荐答案

您不需要地图.只是一个大小为 20 的附加布尔数组.

You don't need a map. Just an additional boolean array with size 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
   }     

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

Now I will expose a straightforward math solution.

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

First sum all numbers in the array. For example you have 5, 1, 4 for the numbers from 1, 2, 3, 4, 5. So 2 and 3 are missing. We can find them easily with math.

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

所以我们知道 x + y = 15 - 10 = 5现在我们将得到第二个方程:

So we know x + y = 15 - 10 = 5 Now we will get a second equation:

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

所以:

x + y = 5
x * y = 6

=> x = 2, y = 3 or x = 3, y = 2 是一样的.

所以 x = 2, y = 3

这篇关于在数组中搜索缺失数字时的性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！