在数字数组中查找缺失数字的最快方法 [英] Quickest way to find missing number in an array of numbers

问题描述

我有一个从 1 到 100(包括两个)的数字数组.数组的大小为100.数字随机添加到数组中，但数组中有一个随机空槽.找到该插槽以及应放入该插槽的数字的最快方法是什么?最好使用 Java 解决方案.

I have an array of numbers from 1 to 100 (both inclusive). The size of the array is 100. The numbers are randomly added to the array, but there is one random empty slot in the array. What is the quickest way to find that slot as well as the number that should be put in the slot? A Java solution is preferable.

推荐答案

您可以在 O(n) 中完成此操作.遍历数组并计算所有数字的总和.现在，从 1 到 N 的自然数之和可以表示为 Nx(N+1)/2.在您的情况下，N=100.

You can do this in O(n). Iterate through the array and compute the sum of all numbers. Now, sum of natural numbers from 1 to N, can be expressed as Nx(N+1)/2. In your case N=100.

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

Subtract the sum of the array from Nx(N+1)/2, where N=100.

那是缺少的数字.在计算总和的迭代过程中可以检测到空槽.

That is the missing number. The empty slot can be detected during the iteration in which the sum is computed.

// 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);

这篇关于在数字数组中查找缺失数字的最快方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！