最快的方式找到数字数组失踪人数 [英] Quickest way to find missing number in an array of numbers

问题描述

我有数字数组1至100（包括两端）。阵列的大小是100中的数字是随机添加到阵列，但阵列中有一个随机空槽。 什么是找到插槽最快的方法以及应该放在插槽的数量？一个Java的解决方案是preferable。

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，可以pssed为 EX $ P $ 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屋！