Найти наименьший положительный недостающее число в массиве

У меня есть массив целых чисел что-то вроде этого:Найти наименьший положительный недостающее число в массиве

[1, 2, 3, 6, 10]

Мой вопрос является то, что это самый простой способ, чтобы получить наименьшую положительное целое число, которое уже не в этом массиве?

Что-то вроде:

[1, 2, 3, 6, 10].lowest_available => 4 
[1, 8, 3, 6, 10].lowest_available => 2 
[5, 8, 3, 6, 10].lowest_available => 1

ли одна иметь представление о том, как справиться с этим в рубин?

источник

2015-03-31 user2945241

что вы подразумеваете под "самым низким доступным"? В '[1, 2, 3, 6, 10]' самое низкое значение равно 1. – shivam

Что такое «псевдо-код»? – sawa

Покажите нам код! – lcguida

По самым низким я имею в виду целое,> 0, а не уже в массиве

В основном вы ищете первое значение, не равное своей index+1 при сортировке. Здесь:

def lowest_available(arr) 
    res = nil 
    arr.sort.each.with_index(1) { |a, i| 
    if i != a 
     res = i 
     break 
    end 
    } 
    res 
end 

lowest_available([1, 2, 3, 6, 10]) 
# => 4 

lowest_available([1, 8, 3, 6, 10]) 
# => 2 

lowest_available([5, 8, 3, 6, 10]) 
# => 1

Обновление

Описанный выше метод может быть сокращено путем возврата значения наряду с break. (Как было предложено Кэри и Стефаном в комментариях ниже).

def lowest_available(arr) 
    arr.sort.find.with_index(1) { |a, i| break i if i != a } 
end

источник

2015-03-31 11:39:26 shivam

Да, это в значительной степени то, за что я пошел ... Я просто думал, если нет такого, что уже сделано для рубина :) – user2945241

Это было замечательное наблюдение за отношениями между каждым значением и его индексом. Два предложения: 1) использовать 'find' и 2) написать' each.with_index (1) '. –

@CarySwoveland, если я использую 'find' в say' .to_enum.with_index (1) .find {| a, i | i! = a} 'он вернет как значение, так и индекс в массиве. Не будет ли запутан выбор индекса из возвращаемого массива? – shivam

Сортировка массива
Итерация по массиву и сравнить значение каждого элемента с текущим индексом + 1, если эта пара не равно вы нашли самое низкое доступное целое число, индекс + 1.

источник

2015-03-31 11:31:19

class Array 
    def lowest_available; (1..Float::INFINITY).find{|e| include?(e).!} end 
end 

[1, 2, 3, 6, 10].lowest_available # => 4 
[1, 8, 3, 6, 10].lowest_available # => 2 
[5, 8, 3, 6, 10].lowest_available # => 1

или, как это было предложено Stefan:

class Array 
    def lowest_available; 1.step.find{|e| include?(e).!} end 
end

источник

2015-03-31 11:51:04 sawa

' (1..Float :: INFINITY) .find' можно выразить как '1.step.find' – Stefan

Есть ли какая-нибудь причина использовать' include? (e).! 'вместо'! include? (e) '? – Stefan

@Stefan 1. Спасибо за предложение. 2. \t Есть ли причина использовать '! Include? (E)' вместо 'include? (E).!'? – sawa

Не то, чтобы элегантно, но если ваши массивы малы, вы можете создать весь целочисленный массив и использовать Array#- найти разницу:

def lowest_available(arr) 
    ((1..arr.size).to_a - arr).first 
end 

lowest_available([1, 2, 3, 6, 10]) #=> 4 
lowest_available([1, 8, 3, 6, 10]) #=> 2 
lowest_available([5, 8, 3, 6, 10]) #=> 1

источник

2015-03-31 12:41:45 Stefan

Другой способ (это поздно):

def first_missing(a) 
    a.reduce(0) { |tot,n| 
    exp=expected(tot); return exp if n>exp; tot + n } 
end 

def expected(tot) 
    ((-1.0 + Math.sqrt(1.0+8*tot))/2).round + 1 
end 

first_missing([1, 2, 3, 6, 10]) #=> 4 
first_missing([1, 8, 3, 6, 10]) #=> 2 
first_missing([5, 8, 3, 6, 10]) #=> 1

источник

2015-04-01 05:59:54

Найти наименьший положительный недостающее число в массиве

ответ

Смежные вопросы