Найдите элементы, отсутствующие в массиве упорядоченных номеров

Question

У меня есть массив array из числа, заказанного. Я определяю число e быть отсутствует из array если:

• Для некоторого элемента v из array, e является либо v + 1 или v - 1,
• e не является элементом array, и
• e не меньше 0.

Например, элементы отсутствуют:

array = [0, 1, 2, 4, 5, 6, 9, 10, 12, 13, 17] 

являются:

[3, 7, 8, 11, 14, 16, 18] 

Как я могу найти элементы отсутствуют в данном массиве array?

Answer 1

Похоже, что вы хотите что-то вроде:

array = [0, 1, 2, 4, 5, 6, 9, 10, 12, 13, 17] 
possible_missing = array.flat_map {|e| [e-1, e+1]}.uniq 
#=> [1, 0, 2, 3, 5, 4, 6, 7, 8, 10, 9, 11, 13, 12, 14, 16, 18] 
diff = (possible_missing - array).select {|e| e >= 0} 
#=> [3, 7, 8, 11, 14, 16, 18] 

Answer 2

Наиболее эффективный способ сделать это, вероятно, будет с inject. Это позволяет построить новый массив в один проход. Это не особенно рубиново, потому что вам нужно написать алгоритм. Вместо того, чтобы полагаться на встроенные функции. Но это, вероятно, самый эффективный способ сделать это.

Следующий алгоритм заканчивает каждую итерацию конечным значением возвращаемого массива, равным n + 1, где n - последний оцениваемый элемент. Если следующий элемент исключит этот элемент, он заменит его на n + 1. Если следующий элемент больше, чем на 2 больше предыдущего, он также вставляет n-1.

present = [0, 1, 2, 4, 5, 6, 9, 10, 12, 13, 17] 

present.inject([]) {|absent,n| 
    # If a number has been skipped at n -1 and n +1 
    if (absent.empty? or absent.last < n - 1) && n > 0 
     absent << n -1 << n + 1 

    # if n-1 is already present or the new array is still empty, add n+1 
    elsif absent.empty? or absent.last == n-1 
     absent << n + 1 

    # if the last element of the absent list should be excluded because it is n, replace it with n+1 
    elsif absent.last == n 
     # replace last absent with next 
     absent[absent.length-1] = n + 1 
     absent 

    # in all other cases do nothing 
    else absent 
    end 
} 

# => [3, 7, 8, 11, 14, 16, 18] 

Answer 3

array = [0, 1, 2, 4, 5, 6, 9, 10, 12, 13, 17] 
range = (0..(array.max + 1)) 
(range.to_a - array).select do |el| 
    [el-1, el+1].any?{|el2| array.include?(el2)} 
end 
# => [3, 7, 8, 11, 14, 16, 18] 

Answer 4

arr = [0, 1, 2, 4, 5, 6, 9, 10, 12, 13, 17] 

b = ([arr[0]-1,0].max..arr[-1]+1).to_a - arr 
    #=> [3, 7, 8, 11, 14, 15, 16, 18] 
(b - b.each_cons(3).with_object([]) { |(c,d,e),f| f << d if e==c+2 }) 
    #=> [3, 7, 8, 11, 14, 16, 18]