搜索数组中缺少的数字时的性能 [英] Performance when searching for missing numbers in array
问题描述
给出是一个列表,其中包含除了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或x = 3,y = 2
相同。
所以 x = 2,y = 3
这篇关于搜索数组中缺少的数字时的性能的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!