排列顺序分配

Question

我正在codility.com上做排列任务。其目的基本上是检查数组传递的元素是否恰好符合其大小的排列。例如，对于array size N，它应该只包含一次1,2,3...N值。我设法得到正确的逻辑，但我的分数在复杂性是可怕的0(N**2)。我该如何改进呢?

def solution(a)
  return 0 unless a.uniq == a
  set = (1..a.size).to_a 
  for n in set
    return 0 unless a.include? n
  end
  1
end

Answer 1

我倾向于这样做。我没有处理a为空或包含除Fixnums以外的元素的可能性。

def solution(a)
  (a.uniq == a && a.min == 1 && a.max == a.size) ? 1 : 0
end
solution([1,2,3,4,5])   #=> 1
solution([1,2,5,3,4])   #=> 1
solution([1,2,3,5,6])   #=> 0
solution([1,2,5,4,2])   #=> 0
solution([1,2,2,4,5])   #=> 0
solution([1,2,5,4,6])   #=> 0

Answer 2

您可以使用另一个数组来跟踪哪些值1..你已经看到了。我不懂ruby，所以这里有一些伪代码

solution(A)
  N = size(A)
  bool[] seen = bool[N]
  for i from 0 to N-1
  {
    number = A[i]
    if (number < 1 || number > N || seen[number])
      return false
  }
  return true;