2

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

给出了一个由 N 个不同整数组成的零索引数组 A。该数组包含 [1..(N + 1)] 范围内的整数，这意味着恰好缺少一个元素。你的目标是找到那个缺失的元素。写一个函数：

类解决方案{公共int解决方案（int [] A）；}

给定一个零索引数组 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)，超出输入存储（不计算输入参数所需的存储）。

可以修改输入数组的元素。

这是我在 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 的大小。但是系统以满分接受了我的答案。我在这里错过了什么吗？

4

5 回答 5

0

我的解决方案从红宝石的角度来看它的基础。

在红宝石中

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

在蟒蛇

def solution(A):
    # write your code in Python 2.7
    return filter(lambda x: (x not in A), range(1, (len(A)+2)))[0]
于 2015-05-21T12:44:40.857 回答
0

该解决方案导致 100/100

def solution(A):

if not A:
    return 1
sumz=sum(xrange(1,(max(A)+1)))
if ((len(A)+1)) not in A:
    return len(A)+1

a_sum=sum(A)

return sumz-a_sum
于 2016-05-26T13:06:10.947 回答
-1

我在 Ruby 中的解决方案。

def solution(a)    
  return 1 if a.empty?
  ac = a.count
  ((ac+1)*(ac+2))/2 - a.inject(0, :+)
end

.inject(0, :+) 对数组中的元素求和。

于 2013-11-23T17:08:03.977 回答
-1

这是两个复杂的场景。

简单地想。

第 1 步：对数组排序 第 2 步：遍历有序数组。如果 A[i] != i+1 你已经资助了缺失的元素。如果循环遍历整个数组而不是最后一个元素丢失，则返回最后一个元素 + 1。

这是 100% 的解决方案。

于 2014-02-08T13:23:38.313 回答
-1

只需启动 lernig Python，这是我的 100 分解决方案：

def solution(A):
    a=[]
    a=A
    a.sort()
    b=0
    if len(a)<1:
        return 1
    if a[0] != 1:
        return 1
    else:
        for x in xrange(0,len(a)):
            b=b+int(a[x])
    if a[len(a)-1]==len(a)+1:        
        c=(1+len(a))*len(a)/2
        d=b-a[len(a)-1]
        e=c-d
        return e
    else:
        return len(a)+1

我知道它不是很好我刚开始学习 Python

于 2014-01-02T15:02:51.450 回答