什么是错的这个解决方案？ （烫发失踪ELEM codility测试） [英] What is wrong with this solution? (Perm-Missing-Elem codility test)

问题描述

我已经开始与codility玩，碰到这个问题就来了：

  

一个零索引数组中的一个由N个不同的整数给出。
  该数组包含在范围内的整数[1 ..（N + 1）]，这意味着
  这正是一个元素丢失。

  
  

您的目标是找到失踪的元素。

  
  

写一个函数：

  INT溶液（INT A []，INT N）;
 

  
  

，给定一个零索引的数组A，返回缺少的值
  元素。

  
  

例如，给定数组A使得：

  
  

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

  
  

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

  
  

假设：

  N是范围[0..100,000]内的整数;
    A的元素都是不同的;
    数组A中的每个元素在该范围内的整数。[1 ..（N + 1）]。
 

  
  

复杂性：

 预计最坏情况下的时间复杂度为O（N）;
    预期的最坏情况的空间复杂度是O（1），超越输入存储（不包括用于输入参数所需要的存储空间）。
 

我已提交下列溶液（PHP）：

 函数溶液（$ A）{
    $ NR =计数（$ A）;
    $ totalSum =（（$ NR + 1）*（$ NR + 2））/ 2;
    $ arrSum = array_sum（$ A）;
    回报（$ totalSum- $ arrSum）;
}
 

这给了我一个得分为100 66，因为它是失败的试验，涉及大型阵列：
large_range范围的序列，长度=〜100,000
其结果：
运行时错误
测试程序意外终止
标准输出：
无效的结果类型，诠释的预期。

我100.000元件阵列本地测试，和它的工作没有任何问题。那么，似乎是我的code中的问题，什么样的测试案例做了codility来回报无效的结果类型，INT预期？

解决方案

它看起来像你打你时，正在执行的乘法PHP变量可以容纳的最大值。我不知道如果PHP允许您使用位工作，但这个问题可以很容易地使用类似于Java的位集合类的东西来解决。

的溶液的主旨在于，因为我们知道，该数字将是1和n之间，在其索引输入数组的元素的变量设置这些位为1。现在有有1通过岗位设置所有位，包括正另一个变量。做这些变量的XOR会给你丢失的数量的位置。

下面是实现上述逻辑（也Codility一个100/100）一个java code

 公众诠释溶液（INT [] A）{
    长期结果= 0L;    位集合all_elements =新的BitSet（）;
    位集合given_elements =新的BitSet（）;    的for（int i = 0; I＆LT;则为a.length;我++）{
        given_elements.set（（int）的A [i]）;
    }    的for（int i = 1; I＆LT; =则为a.length + 1;我++）{
        all_elements.set（ⅰ）;
    }    all_elements.xor（given_elements）;    的for（int i = 0; I＆LT; all_elements.length（）; ++ I）{
        如果（all_elements.get（ⅰ））{
            结果= I;
            打破;
        }
    }    回报（INT）结果;
}
 

I have started playing with codility and came across this problem:

A zero-indexed array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

int solution(int A[], int N); 

that, given a zero-indexed array A, returns the value of the missing element.

For example, given array A such that:

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

the function should return 4, as it is the missing element.

Assume that:

    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)].

Complexity:

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

I have submitted the following solution (in PHP):

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

which gave me a score of 66 of 100, because it was failing the test involving large arrays: "large_range range sequence, length = ~100,000" with the result: RUNTIME ERROR tested program terminated unexpectedly stdout: Invalid result type, int expected.

I tested locally with an array of 100.000 elements, and it worked without any problems. So, what seems to be the problem with my code and what kind of test cases did codility use to return "Invalid result type, int expected"?

解决方案

It looks like you are hitting the maximum value a PHP variable can hold when you are performing the multiplication. I am not sure if PHP allows you to work with bits, but this problem can be solved easily using something similar to Java's BitSet class.

The gist of the solution is, since we know that the numbers will be between 1 and n, set those bits to 1 in a variable whose indices are the elements of the input array. Now have another variable which has all the bits set in positions, 1 through and including n. Doing an XOR of these variables will give you the position of the missing number.

Here is a java code that implements the above logic (also a 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;
}

这篇关于什么是错的这个解决方案？ （烫发失踪ELEM codility测试）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！