所以我正在检查 codibility 网站以进行在线代码评估。我尝试了演示示例 http://codility.com/c/intro/demoRVC9C9-W8X熟悉系统。

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:

class Solution { public int solution(int[] A); }

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

Elements of input arrays can be modified.

这是我在 Python 中的解决方案:

def solution(A): 
  tmp = [ 0 for x in xrange( len(A) + 1 ) ] 
  for i,x in enumerate( A ): 
    tmp[ x - 1 ] = 1 
  return 1 + tmp.index( 0 )

我很确定我的解决方案不会被接受，因为空间复杂度为 O(n)，其中 n 是 A 的大小。但是系统以满分接受了我的答案。我在这里遗漏了什么吗？

请您参考如下方法:

我的解决方案从 ruby 的角度考虑它的基础。

ruby

def solution(a) 
  (1..(a.count+1)).select{|x| !a.include?(x)}.first 
end

在 python 中

def solution(A): 
    # write your code in Python 2.7 
    return filter(lambda x: (x not in A), range(1, (len(A)+2)))[0]

python之一个简单例子的空间复杂度

ruby

在 python 中