php - 这个解决方案有什么问题？（Perm-Missing-Elem 代码测试）

Question

我已经开始玩 codility 并遇到了这个问题：

给出了一个由 N 个不同整数组成的零索引数组 A。该数组包含 [1..(N + 1)] 范围内的整数，这意味着恰好缺少一个元素。

你的目标是找到那个缺失的元素。

写一个函数：
int solution(int A[], int N); 
给定一个零索引数组 A，返回缺失元素的值。

例如，给定数组 A 使得：

A[0] = 2 A[1] = 3 A[2] = 1 A[3] = 5

该函数应返回 4，因为它是缺少的元素。

假使，假设：
    N is an integer within the range [0..100,000];
    the elements of A are all distinct;
    each element of array A is an integer within the range [1..(N + 1)].
复杂：
    expected worst-case time complexity is O(N);
    expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

我已经提交了以下解决方案（在 PHP 中）：

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

这给了我 100 分中的 66 分，因为它未能通过涉及大型数组的测试：“large_range 范围序列，长度 = ~100,000”，结果为：RUNTIME ERROR 测试程序意外终止 stdout：无效的结果类型，预期为 int。

我用 100.000 个元素的数组在本地进行了测试，它没有任何问题。那么，我的代码似乎有什么问题，以及 codility 使用什么样的测试用例来返回“无效的结果类型，预期的 int”？

score 8 · Accepted Answer

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

score 3 · Accepted Answer

其他人已经回答了最初的问题，但我想对这个问题提供一些更深入的了解，并分享一个快速的 C++ 替代解决方案。

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

由于 N>65,536 的乘法超过 32 位精度，OP 遇到了整数溢出问题。对于给定的 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;
}

score 2 · Accepted Answer

执行乘法时，您似乎达到了 PHP 变量可以容纳的最大值。我不确定 PHP 是否允许您使用位，但是可以使用类似于 Java 的BitSet类的东西轻松解决这个问题。

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

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

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;
}

score 1 · Accepted Answer

使用 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)) ;

}

score 1 · Accepted Answer

考虑一下 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

score 1 · Accepted Answer

我是stackoverflow的新手，试图以格式化的方式放置。这是我在 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;
    }

score 1 · Accepted Answer

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

score 0 · Accepted Answer

我对这个问题的 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

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

score 0 · Accepted Answer

100% 分数：对于 Perm Missing Codility

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

score 0 · Accepted Answer

虽然我只有 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;
}

score 0 · Accepted Answer

短一点的 1 行 PHP 解决方案 100/100 PermMissingElem：

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

score 0 · Accepted Answer

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 解决方案

score 0 · Accepted Answer

有史以来的第一个贡献（交叉手指使其正确！）。我对 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);
}

无需包含其他库；-)。希望对大家有帮助！

score 0 · Accepted Answer

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

我最初对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;

score 0 · Accepted Answer

我在 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);

}

score 0 · Accepted Answer

请查看我的解决方案，我的时间复杂度是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;

}

score 0 · Accepted Answer

简短的 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 );
}

score 0 · Accepted Answer

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;
}

score 0 · Accepted Answer

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;

}

score 0 · Accepted Answer

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

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;
}

score 0 · Accepted Answer

这个简单的解决方案得分 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;
}

score 0 · Accepted Answer

这是我的 PHP 解决方案：

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

score 0 · Accepted Answer

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;
}

score 0 · Accepted Answer

最快的方式：

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

score 0 · Accepted Answer

叹息，我不得不承认这很有趣... 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);
}

score 0 · Accepted Answer

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>());
}

score 0 · Accepted Answer

我找到了一个使用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;
    }
}

score 0 · Accepted Answer

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

 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;
}

score 0 · Accepted Answer

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

score -1 · Accepted Answer

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;
    }

php - 这个解决方案有什么问题？（Perm-Missing-Elem 代码测试）

30 回答 30

Related

Reference