这个解决方案有什么问题?(烫发缺失-埃莱姆编码测试）

function solution($A) {
    $nr = count($A);
    $totalSum = (($nr+1)*($nr+2))/2;
    $arrSum = array_sum($A);
    return ($totalSum-$arrSum);
}

PermMissingElem的100/100 php解决方案：

function solution($A) {   
    $N   = count($A);
    $sum = ($N + 2) * ($N + 1) / 2;
    for($i = 0; $i < $N; $i++){
        $sum -= $A[$i];
    }
    return intval($sum);
}

其他人已经回答了最初的问题，但我想提供对问题的更多见解，并在C++中分享一种快速的替代解决方案。

当然，解决方案是基于古老的算术技巧，将一大组连续的数字相加，著名的归功于卡尔·弗里德里希·高斯（Carl Friedrich Gauss），他在小时候发现了它。

OP 遇到了整数溢出问题，因为 N>65,536 的乘法超过 32 位精度。这里有一个小技巧可以避免在给定的N = [0..100,000]范围内发生这种情况。当计算 [1..N+1] 中数字的所有整数（高斯和）的总和时，我们减去 （N+2）/2 的偏移量，使其成为零和（或者在 N 为奇数的情况下最多"偏移"）。同样，我们也从数组中的所有值中减去这个偏移量。这样，我们将要添加的数字范围最多移动到 [-50,000...+50,000]。在最坏的情况下，即如果所有正（或负）范围数字都是按顺序排列的，则最大的中间和永远不会超过 31 位，因此不会发生溢出。对于交错的正数和负数，中间和将更小。

从高斯和中减去数组总和后，我们再次通过添加回偏移量来更正以找到缺少的数组元素。

这是 C++ 中的代码（它在编码测试中得分为 100%）：

int solution(vector<int> &A) {
    int N;
    int sum;
    int gauss;              // sum of all ints in [1..N+1] using Gauss' trick
    int offset;             // subtract offset from all numbers to make it a zero-sum
    int num_x;

    N = int(A.size());      // convert from size_t to int
    sum = 0;
    offset = (N+2) >> 1;        // make range symmetric between [-N/2..N/2] to avoid integer overflow in Gauss sum for large N
    // "gauss" should nominally be a zero sum, but if N is odd then N/2 is truncated 
    // and offset is off by 1/2 for each of the N elements. This formula compensates for that.
    gauss = (N & 1) * offset;
    for (int i = 0; i < N; i++) {
        sum += (A[i] - offset);     // this is the O(n) part of summing all elements in the array
    }
    num_x = gauss - sum + offset;   // find the missing number
    return num_x;
}

看起来您正在达到执行乘法时 PHP 变量可以保持的最大值。我不确定PHP是否允许你使用bits，但是使用类似于Java的BitSet类的东西可以轻松解决这个问题。

解决方案的要点是，由于我们知道数字将介于 1 和 n 之间，因此在索引是输入数组元素的变量中将这些位设置为 1。现在有另一个变量，它的所有位都设置在位置上，从 1 到包括 n。对这些变量进行异或运算将为您提供缺失数字的位置。

这是一个实现上述逻辑的java代码（也是Codility上的100/100）

public int solution(int[] A) {
    long result = 0L;
    BitSet all_elements = new BitSet();
    BitSet given_elements = new BitSet();
    for (int i = 0; i < A.length; i++) {
        given_elements.set((int) A[i]);
    }
    for (int i = 1; i <= A.length + 1; i++) {
        all_elements.set(i);
    }
    all_elements.xor(given_elements);
    for (int i = 0; i < all_elements.length(); ++i) {
        if(all_elements.get(i)) {
            result = i;
            break;
        }
    }
    return (int)result;
}

我是

堆栈溢出的新手，试图以格式化的方式放置。这是我在 java 中的答案，得分为 100/100......具有 O（n） 复杂性。如果您愿意，可以在以下链接中看到它。http://codility.com/demo/results/demoJJERZ4-E7Z/

public int solution(int[] A) {
        int len = A.length;
    int result = 0;
         int[] B;
         B = new int[len+1];
         for(int i=0; i<= B.length-1; i++)
         {
            B[i] = i+1;
         }
              // int n = len +1;
                int i, sum1 = 0, sum2 = 0;
                for (i = 0; i <= A.length-1; i++) {
                        sum1 = sum1 + A[i];
                }
                for (i = 0; i <= B.length-1; i++) {
                        sum2 = sum2 + B[i];
                }
               result = sum2 - sum1;
                return result;
    }

考虑 Ruby 中的这个 100/100 解决方案：

# Algorithm:
#
# * Compute theoretical sum based on array size.
# * Compute actual sum.
# * Subtract one from the other and you get the missing element.
def solution(ar)
  # Trivial case.
  return 1 if ar.empty?
  size = ar.size + 1
  full_sum = (size*(size + 1))/2
  actual_sum = ar.inject(:+)
  # Result.
  full_sum - actual_sum
end
#--------------------------------------- Tests
def test
  sets = []
  sets << ["empty", 1, []]
  sets << ["12", 3, [1, 2]]
  sets << ["13", 2, [1, 3]]
  sets << ["sample", 4, [2, 3, 1, 5]]
  sets.each do |name, expected, ar|
    out = solution(ar)
    raise "FAILURE at test #{name.inspect}: #{out.inspect} != #{expected.inspect}" if out != expected
  end
  puts "SUCCESS: All tests passed"
end

用PHP编码：我得到了（100%）

函数解决方案（$A） {

$arraySum=0;
$totalSum=0;
$res = 0;
for($i=0;$i<count($A);$i++)
{
    $arraySum += $A[$i];
    $totalSum += $i+1 ;
}
$totalSum += $i+1 ;
return abs((int)($totalSum - $arraySum)) ; 

}

Python 中的 100

/100 解决方案。只有3行，易于理解。

def solution(A):
    sum1 = sum(range(1,len(A)+2))
    sum2 = sum(A)
    return sum1-sum2

对于大型阵列，上述解决方案效率不高，有时可能无法正常工作。建议的改进解决方案将适用于所有极端情况。请注意，在这种情况下，我们只遍历数组一次。因此，该解决方案针对空间和时间复杂性进行了优化。

def solution(A):
    size = 0
    array_sum = 0
    for item in A:
        size += 1
        array_sum += item
    expected_sum = (size+1)*(size+2)/2
    return expected_sum - array_sum

请查看我的解决方案，我的时间复杂度是O（N），时间复杂度是O（N），分数是100。

int solution(int A[], int N) {
int * p = (int *)malloc((N + 1)*sizeof(int));
memset(p, 0, (N + 1)*sizeof(int));
int i;
int ret = 0;
for (i = 0; i < N; i++)
{
    A[i] = A[i] - 1;
}
for (i = 0; i < N; i++)
{
    p[A[i]] = 1;    
}
for (i = 0; i <= N; i++)
{
    if(p[i] == 0)
    {
        ret = i + 1;
        break;
    }
}
free(p);
return ret;

}

PermMissingElem的100/100 Objective C解决方案：

int solution(NSMutableArray *A) {
    unsigned long length = [A count] + 1;
    unsigned long sum1 = 0;
    unsigned long sum2 = 0;
    for (int i=0; i < [A count]; i++) {
        sum1 += [[A objectAtIndex:i] longValue];
    }
    sum2 = ((((length+1)*length)/2) - sum1);
    return sum2;
}

PermMissingElem的另一个C解决方案（在Codility上得分为100/100）：

#include <math.h>
int solution(int A[], int N) {
double sum = (pow(N, 2) + 3 * N + 2) / 2;
int i;
for (i = 0; i < N; i++) {
    sum -= A[i];
}
return (int)sum;
}

有史以来的第一个贡献（交叉手指使其正确！我的C++解决方案如下：

int solution(int A[], int N)
{
    int sum = 0;
    for(int i=0; i<N; i++)
    {
        sum+= (i+1) - A[i];
    }
    sum+=(N+1);
    return(sum);
}

无需包含其他库;-）。希望对大家有所帮助！

这是我的解决方案。它基本上循环遍历数组，将各个元素设置为零。处理数组后，非零元素的索引指示缺失值。

void f( vector<int> &A, int i )
{
    if( i != A.size()+1 &&  i != 0 )
    {
        int j = A[i-1];
        A[i-1] = 0;
        f(A, j);
    }
}
int solution(vector<int> &A) 
{   
    for ( int i = 0; i < A.size(); i++)
    {
        f(A, A[i]);
    }
    for( int i = 0; i < A.size(); i++)
   {
       if(A[i] != 0)
        return i+1;
   } 
   return A.size()+1;
}

100% 分数：对于烫发缺少编码

function solution($A){
    return intval(intval(((count($A)+1) * ((count($A)+1) + 1)) / 2) - intval(array_sum($A)));
}

虽然我只:(得到了 80 分......但它奏效了

int solution(int A[], int N) {
    int ret, nsum, i, sum = 0;
    nsum=(N * (N + 1)) / 2;
    for(i = 0; i < N; i++){
       sum = sum + A[i];
    }
    sum = (sum - (N + 1));
    ret = sum - nsum;
    return ret;
}

这个简单的解决方案得分为100%：

int solution(int A[], int N) {
  // write your code in C90
  double sum = N/2.;
  int i;
  double sumA=0;
  for(i=0; i<N; ++i) {
    sumA += A[i] - N/2.;
  }
  sumA -= N+1;
  return sum - sumA;
}

哇，这里有一些非常好的答案......

我最初的 JavaScript 100% 不是测试要求的 O（1） 空间复杂度：

var ll = A.length, lookup = {};
for (i=0; i<ll; i++)
   lookup[A[i]] = true;
for (i=0; i<ll; i++)
   if (!lookup[i+1]) return i+1;

来到这里并看到优秀的帖子后，我选择了Daniel Caballero的代码，由vaxquis简化为Javascript并粘贴到此处以供将来欣赏：

var N = A.length, sum = 2*N + 1, i; 
for (i = N-1; i >= 0; i--) 
   sum += (i-A[i]); 
return sum; 

简短C++答案，考试成绩 100%

#include<numeric>
int solution(vector<int> &A) {
    // compute sum of all elements, needs <numeric>
    long long sum = std::accumulate(A.begin(), A.end(), 0);
    // number of elements as 64-bit int to avoid overflow for large arrays
    long long N =  static_cast<long long>(A.size());
    // missing element is sum of elems 1 to N+1 minus sum, cast to int
    return static_cast<int>( ((N+1)*(N+2))/2 - sum );
}

function solution($A) {
    $sum = array_sum($A);
    $sum2 = 0;
    for ($i = 1; $i <= count($A)+1; $i++) {
        $sum2 += $i;
    }
    return $sum2-$sum;
}

PHP 100

/100 解决方案

我在 O（N） 或 O（N * log（N）） PHP 中的 100/100 解决方案

function solution($A) {
    $right = 0;
    $count = count($A);
    $left = 0;

    for ($i = 0; $i < $count; $i++) {
        $right += $A[$i];
        $left += ($i + 1);
    }
    $left += $count;
    return (int)(abs(($right - $left))+1);
}

短一点 1 行 PHP 解决方案 100/100 PermMissing Elem：

function solution($a) {
    return array_sum(range(1, count($a)+1)) - array_sum($a);
}

我的PHP解决方案：100/100分数

function solution($a) {   
$c   = count($a); // counting the elements
$sum = ($c + 2) * ($c + 1) / 2; // getting the elements sum
$s = array_sum($A); // taking the sum of actual array elements
return intval($sum - $s ); //returning the difference
}//end of solution

最好的问候，希望这有帮助

PHP 中的 100

/100 和第 n 个三角形数的可读性更强的实现

function solution($a)
{
   $array_count = count($a) + 1;
   $sum = (($array_count + 1) * $array_count) / 2;
   $result = $sum - array_sum($a);
   return $result;
}

int solution(int []A){
    //missing number is sum of all possible entries ([1..N+1]) minus
    //sum of all items in A that are with the constrain [1..N+1] 
    int N = A.length;
    long sum = 0L;
    for(int i=1;i<=N+1;i++){
        sum += i;
    }
    long sumPossible= 0L;
    for(int i=0; i<N;i++){
        int x = A[i];
        boolean outOfRange = x<1 || x>N+1;
        if(!outOfRange) {
            sumPossible += x;
        }
    }
    return (int)(sum-sumPossible);
}

C++单行 100/100 解决方案：

#include <algorithm>
#include <functional>
int solution(vector<int> &A) {
    return std::accumulate(A.begin(), A.end(), (A.size()+1) * (A.size()+2) / 2, std::minus<int>());
}

叹气，我不得不承认这很有趣......N+1 个整数的总和

= （N+1）（N+2）/2 = N [（N+2）/2] + （N+2）/2 = N * 因子 + 因子，其中因子 = （N+2）/2。得分 100

/100检测到的时间复杂度：O（N） 或 O（N * log（N））

int solution(int A[], int N) {    
    int factor = N+2;
    int total = factor;             
    for (int i=0;i<N;i++){        
        total += (factor - (A[i]<<1));                
    }    
    return (total>>1)+(total&1);
}

这是我的PHP解决方案：

function solution($A) {   
    $n = count($A) + 1;
    return (($n * ($n + 1)) / 2) - (array_sum($A));
}

最快的方法：

function solution($A){
   $arr2 = range(1, max($A));
   $missing = array_diff($arr2, $A);
}

我找到了一个使用 binarySearch 在 java 中得分为 100/100 的解决方案。

这是代码：

import java.util.*;
class Solution {
    public int solution(int[] A) {
        Arrays.sort(A);
        int i = 1;
        while (i <= A.length) {
            int res = Arrays.binarySearch(A, i); 
            if (res < 0) {
                return i;
            }
            i++;
        }
        return i;
    }
}

这是一个数学问题。使用序列的总和，求和到最后一项

 Sn = n /2 * (a + l) 

where a is the first term i.e. 1, n = the last number i.e. (array length + 1)

实际总和

与计算数组总和之间的差异是缺少的元素。

Javascript版本：100%分数

function solution(A) {    
    //approach question using series
    //find the sum to the last term
    let lastNumb = A.length + 1;
    let sumOfSeries = ((1 + lastNumb) * lastNumb) / 2;
    
    //sum the numbers in the array
    let arraySum = A.reduce((accum,val)=>accum+val,0);
    //the missing number is the difference between
    //the array sum and the expected sum
    return sumOfSeries - arraySum;
}

public static int solution(int[] A)
    {
        int Min = A.Min();
        int Max = A.Max();
        for (int i = Min; i < Max; i++)
        {
            if (A.Where(t => t == Min+i).ToArray().Length == 0)
            {
                return Min+i;
            }
        }
        return Min-1;
    }