在数组中查找缺失数字的最快方法

Question

我有一个从1到100(包括两者)的数字数组.数组的大小为100.数字随机添加到数组中,但数组中有一个随机空插槽.找到该插槽的最快捷方式是什么,以及插入插槽的数量是多少？Java解决方案更可取.

Answer 1

你可以在O(n)中做到这一点.迭代数组并计算所有数字的总和.现在,从1到N的自然数之和可以表示为Nx(N+1)/2.在你的情况下N = 100.

从中减去数组的总和Nx(N+1)/2,其中N = 100.

这是缺少的数字.可以在迭代期间检测空时隙,其中计算总和.

// will be the sum of the numbers in the array.
int sum = 0;
int idx = -1;
for (int i = 0; i < arr.length; i++)
{
    if (arr[i] == 0)
    {
         idx = i; 
    }
    else 
    {
         sum += arr[i];
    }
}

// the total sum of numbers between 1 and arr.length.
int total = (arr.length + 1) * arr.length / 2;

System.out.println("missing number is: " + (total - sum) + " at index " + idx);

Answer 2

我们可以使用比求和更安全的XOR运算,因为在编程语言中如果给定的输入很大,它可能会溢出并可能给出错误的答案.

在进入解决方案之前,请知道A xor A = 0.因此,如果我们将两个相同的数字相异,则该值为0.

现在,对阵列中存在的元素进行异或[1..n]取消相同的数字.所以最后我们会得到丢失的号码.

// Assuming that the array contains 99 distinct integers between 1..99
// and empty slot value is zero
int XOR = 0;
for(int i=0; i<100; i++) {
    if (ARRAY[i] != 0) // remove this condition keeping the body if no zero slot
        XOR ^= ARRAY[i];
    XOR ^= (i + 1);
}
return XOR;
//return XOR ^ ARRAY.length + 1; if your array doesn't have empty zero slot. 

Answer 3

让给定的数组为A,长度为N.让我们假设在给定的数组中,单个空槽用0填充.

我们可以使用许多方法找到解决这个问题的方法,包括使用的算法Counting sort.但是,就有效的时间和空间使用而言,我们有两种算法.一个主要使用求和,减法和乘法.另一个使用XOR.数学上两种方法都可以正常工作.但是以编程方式,我们需要用主要措施来评估所有算法

• 限制(如输入值大(A[1...N])和/或输入值的数量很大(N))
• 涉及的条件检查次数
• 涉及的数学运算的数量和类型

这是因为时间和/或硬件(硬件资源限制)和/或软件(操作系统限制,编程语言限制等)等方面的限制.让我们列出并评估每一个的利弊. .

算法1:

在算法1中,我们有3个实现.

1. 使用数学公式(1+2+3+...+N=(N(N+1))/2)计算所有数字的总和(包括未知缺失数).在这里,N=100.计算所有给定数字的总和.从第一个结果中减去第二个结果将给出缺失的数字.

   Missing Number = (N(N+1))/2) - (A[1]+A[2]+...+A[100])

2. 使用数学公式(1+2+3+...+N=(N(N+1))/2)计算所有数字的总和(包括未知缺失数).在这里,N=100.从该结果中,减去每个给定的数字给出缺失的数字.

   Missing Number = (N(N+1))/2)-A[1]-A[2]-...-A[100]

   (Note:尽管第二个实现的公式是从第一个派生的,但从数学的角度来看两者都是相同的.但是从编程的角度来看两者都是不同的,因为第一个公式比第二个公式更容易出现位溢出(如果给定的数字虽然加法比减法更快,但第二种实现方式减少了由于加入大值而引起的位溢出的可能性(它没有完全消除,因为N+1公式中存在很少的机会因为()但两者同样容易因乘法而出现比特溢出.限制是两种实现只有在给出正确结果的情况下N(N+1)<=MAXIMUM_NUMBER_VALUE.对于第一种实现,额外的限制是它只在给出正确的结果Sum of all given numbers<=MAXIMUM_NUMBER_VALUE.)

3. 计算所有数字的总和(这包括未知的缺失数字)并并行地减去同一循环中的每个给定数字.这消除了乘法引起位溢出的风险,但是通过加法和减法容易出现位溢出.

   //ALGORITHM missingNumber = 0; foreach(index from 1 to N) { missingNumber = missingNumber + index; //Since, the empty slot is filled with 0, //this extra condition which is executed for N times is not required. //But for the sake of understanding of algorithm purpose lets put it. if (inputArray[index] != 0) missingNumber = missingNumber - inputArray[index]; }

在编程语言(如C,C++,Java等)中,如果表示整数数据类型的位数有限,则由于求和,减法和乘法,所有上述实现都容易出现位溢出,从而导致错误的结果在大输入值(A[1...N])和/或大量输入值(N)的情况下.

算法2:

我们可以使用XOR的属性来解决这个问题,而不必担心位溢出的问题.而且XOR比求和更安全,更快.我们知道XOR的属性,两个相同数字的XOR等于0(A XOR A = 0).如果我们计算从1到N的所有数字的XOR(这包括未知的缺失数字),然后结果,XOR所有给定的数字,公共数字被取消(自A XOR A=0),最后我们得到了失踪数.如果我们没有位溢出问题,我们可以使用求和和基于XOR的算法来获得解决方案.但是,使用XOR的算法比使用求和,减法和乘法的算法更安全,更快速.并且我们可以避免由求和,减法和乘法引起的额外担忧.

在算法1的所有实现中,我们可以使用XOR而不是加法和减法.

让我们假设, XOR(1...N) = XOR of all numbers from 1 to N

实施1 => Missing Number = XOR(1...N) XOR (A[1] XOR A[2] XOR...XOR A[100])

实施2 => Missing Number = XOR(1...N) XOR A[1] XOR A[2] XOR...XOR A[100]

实施3 =>

//ALGORITHM
missingNumber = 0;
foreach(index from 1 to N)
{
    missingNumber = missingNumber XOR index;
    //Since, the empty slot is filled with 0,
    //this extra condition which is executed for N times is not required.
    //But for the sake of understanding of algorithm purpose lets put it.
    if (inputArray[index] != 0)
        missingNumber = missingNumber XOR inputArray[index];
}

算法2的所有三种实现都可以正常工作(从编程的角度来看也是如此).一个优化是,类似于

1+2+....+N = (N(N+1))/2

我们有,

1 XOR 2 XOR .... XOR N = {N if REMAINDER(N/4)=0, 1 if REMAINDER(N/4)=1, N+1 if REMAINDER(N/4)=2, 0 if REMAINDER(N/4)=3}

我们可以通过数学归纳证明这一点.因此,我们可以使用此公式来减少XOR运算的数量,而不是通过XOR将所有数字从1到N计算为XOR(1 ... N)的值.

此外,使用上述公式计算XOR(1 ... N)具有两种实现方式.实施明智,计算

// Thanks to https://a3nm.net/blog/xor.html for this implementation
xor = (n>>1)&1 ^ (((n&1)>0)?1:n)

比计算更快

xor = (n % 4 == 0) ? n : (n % 4 == 1) ? 1 : (n % 4 == 2) ? n + 1 : 0;

那么,优化的Java代码是,

long n = 100;
long a[] = new long[n];

//XOR of all numbers from 1 to n
// n%4 == 0 ---> n
// n%4 == 1 ---> 1
// n%4 == 2 ---> n + 1
// n%4 == 3 ---> 0

//Slower way of implementing the formula
// long xor = (n % 4 == 0) ? n : (n % 4 == 1) ? 1 : (n % 4 == 2) ? n + 1 : 0;
//Faster way of implementing the formula
// long xor = (n>>1)&1 ^ (((n&1)>0)?1:n);
long xor = (n>>1)&1 ^ (((n&1)>0)?1:n);

for (long i = 0; i < n; i++)
{
    xor = xor ^ a[i];
}
//Missing number
System.out.println(xor);

Answer 4

这是一个亚马逊的采访问题,最初在这里回答:我们将数字从1到52放入一个51数字阵列中,找出哪个数字缺失的最佳方法是什么？

答案如下:

1) Calculate the sum of all numbers stored in the array of size 51. 
2) Subtract the sum from (52 * 53)/2 ---- Formula : n * (n + 1) / 2.

它也在这里写博客:软件工作 - 面试问题

Answer 5

这是一个简单的程序,用于查找整数数组中缺少的数字

ArrayList<Integer> arr = new ArrayList<Integer>();
int a[] = { 1,3,4,5,6,7,10 };
int j = a[0];
for (int i=0;i<a.length;i++)
{
    if (j==a[i])
    {
        j++;
        continue;
    }
    else
    {
        arr.add(j);
        i--;
    j++;
    }
}
System.out.println("missing numbers are ");
for(int r : arr)
{
    System.out.println(" " + r);
}

Answer 6

5050 - (数组中所有值的总和)=缺少数字

int sum = 0;
int idx = -1;
for (int i = 0; i < arr.length; i++) {
  if (arr[i] == 0) idx = i; else sum += arr[i];
}
System.out.println("missing number is: " + (5050 - sum) + " at index " + idx);

Answer 7

最近我在求职面试中遇到了一个类似（不完全相同）的问题，而且我从一个朋友那里听说在面试中被问到完全相同的问题。因此，这里是 OP 问题的答案以及可能会提出的更多变体。答案示例是在Java中给出的，因为它指出：

最好使用 Java 解决方案。

变化1：

从 1 到 100 的数字数组（包括两者）... 数字随机添加到数组中，但数组中有一个随机空槽

public static int findMissing1(int [] arr){
    int sum = 0;
    for(int n : arr){
        sum += n;
    }
    return (100*(100+1)/2) - sum;
}

说明： 此解决方案（与此处发布的许多其他解决方案一样）基于 的公式Triangular number，该公式为我们提供了从 1 到n（在本例中n为 100）的所有自然数的总和。现在我们知道应该从 1 到 100 的总和 - 我们只需要减去给定数组中现有数字的实际总和。

变体2：

从 1 到 n 的数字数组（意味着最大数字未知）

public static int findMissing2(int [] arr){
    int sum = 0, max = 0;
    for(int n : arr){
        sum += n;
        if(n > max) max = n;
    }
    return (max*(max+1)/2) - sum;
}

说明： 在这个解决方案中，由于没有给出最大数量 - 我们需要找到它。找到最大数量后 - 逻辑是相同的。

变化3：

从 1 到 n 的数字数组（最大数未知），数组中有两个随机空槽

public static int [] findMissing3(int [] arr){
    int sum = 0, max = 0, misSum;
    int [] misNums = {};//empty by default
    for(int n : arr){
        sum += n;
        if(n > max) max = n;
    }
    misSum = (max*(max+1)/2) - sum;//Sum of two missing numbers
    for(int n = Math.min(misSum, max-1); n > 1; n--){
        if(!contains(n, arr)){
            misNums = new int[]{n, misSum-n};
            break;   
        }
    }
    return misNums;
}
private static boolean contains(int num, int [] arr){
    for(int n : arr){
        if(n == num)return true;
    }
    return false;
}

说明： 在此解决方案中，未给出最大数字（如前文所述），但也可能缺少两个数字而不是一个。所以首先我们找到缺失数字的总和 - 与之前的逻辑相同。其次找到丢失的总和和最后一个（可能）丢失的数字之间的较小数字 - 以减少不必要的搜索。第三，由于Javas Array（不是 Collection）没有方法 as indexOfor contains，我为该逻辑添加了一个小的可重用方法。第四当找到第一个缺失的数字时，第二个是从缺失的总和中减去。如果仅缺少一个数字，则数组中的第二个数字将为零。

变化4：

从 1 到 n 的数字数组（最大数字未知），缺少 X（丢失数字的数量未知）

public static ArrayList<Integer> findMissing4(ArrayList<Integer> arr){
    int max = 0;
    ArrayList<Integer> misNums = new ArrayList();
    int [] neededNums;
    for(int n : arr){
        if(n > max) max = n;
    }
    neededNums = new int[max];//zero for any needed num
    for(int n : arr){//iterate again
        neededNums[n == max ? 0 : n]++;//add one - used as index in second array (convert max to zero)
    }
    for(int i=neededNums.length-1; i>0; i--){
        if(neededNums[i] < 1)misNums.add(i);//if value is zero, than index is a missing number
    }
    return misNums;
}

说明： 在此解决方案中，与前一个一样，最大数量未知，可能会丢失多个数字，但在此变体中，我们不知道有多少数字可能丢失（如果有）。逻辑的开始是相同的 - 找到最大数量。然后我用零初始化另一个数组，在这个数组中index表示可能丢失的数字，零表示数字丢失。因此，原始数组中的每个现有数字都用作索引，其值递增 1（最大值转换为零）。

笔记

如果您想要其他语言的示例或此问题的其他有趣变体，欢迎您查看我的Github存储库以获取面试问题和答案。