php - このソリューションの何が問題になっていますか? (Perm-Missing-Elem の好感度テスト)

Question

私は誠実に遊び始め、この問題に遭遇しました：

N 個の異なる整数からなるゼロインデックスの配列 A が与えられます。配列には [1..(N + 1)] の範囲の整数が含まれています。これは、ちょうど 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 range sequence, length = ~100,000" という結果でした: RUNTIME ERROR でテストされたプログラムが予期せずに終了しました stdout: Invalid result type, int expected.

100.000 要素の配列を使用してローカルでテストしましたが、問題なく動作しました。それで、私のコードの問題と思われるものと、「無効な結果タイプ、int が期待されます」を返すために codility が使用したテストケースの種類は何ですか?

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++ で高速な代替ソリューションを共有することを考えました。

もちろん、解決策は、連続した数の大きなセットを合計する古い算術のトリックに基づいています。これは、幼い頃にカール・フリードリッヒ・ガウスが発見したことで有名です。

OP は、N>65,536 の 32 ビット精度を超える乗算による整数オーバーフローの問題に遭遇しました。N = [0..100,000] の指定された範囲でそれを回避するためのちょっとしたトリックを次に示します。[1..N+1] の数値のすべての int の合計 (ガウス合計) を計算するとき、(N+2)/2 のオフセットを減算してゼロサムにします (または最大で「オフセット」ケース N は奇数)。同様に、配列内のすべての値からこのオフセットも減算します。このようにして、加算する数値の範囲を最大 [-50,000...+50,000] にシフトします。最悪の場合、つまり、すべての正 (または負) の範囲の数値が連続している場合、最大の中間和が 31 ビットを超えることはないため、オーバーフローは発生しません。インターリーブされた正と負の数値の場合、中間の合計はさらに小さくなります。

配列の合計を Gauss の合計から差し引いた後、欠落している配列要素を見つけるためにオフセットを追加して再度修正します。

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

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

Python での 100/100 ソリューション。たった3行でわかりやすい。

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

大きな配列の場合、上記の解決策は効率的ではなく、うまくいかない場合もあります。提案された改善されたソリューションは、すべてのコーナーケースで機能します。この場合、配列を 1 回だけ反復処理していることに注意してください。したがって、このソリューションは、空間と時間の両方の複雑さに対して最適化されています。

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 1 · Accepted Answer

私はstackoverflowが初めてで、フォーマットされた方法で入れようとしました。これが、100/100 スコアの Java での私の答えです.......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 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

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

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

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

私は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

史上初の貢献 (正しいことをするために指を交差させてください!)。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

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

少し短い 1 行の PHP ソリューション 100/100 PermMissingElem:

function solution($a) {
    return array_sum(range(1, count($a)+1)) - array_sum($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

うわー、ここにいくつかの本当に良い答えがあります...

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

これは私のPHPソリューションです:

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

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

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

これが私の解決策です。基本的に、それぞれの要素をゼロに設定する配列をループします。配列が処理されると、ゼロ以外の要素のインデックスは欠損値を示します。

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