Объяснение проблемы

Учитывая массив целых чисел, найдите самый длинный подмассив, в котором абсолютная разница между любыми двумя элементами меньше или равна 1.

Пример a = [1,1,2,2,4,4,5,5,5] Есть два подмассива, удовлетворяющие критерию: [1,1,2,2] и [4,4,5,5,5]. Подмассив максимальной длины состоит из 5 элементов.

pickingNumbers имеет следующие параметры(ы):

• int a[n]: массив целых чисел

ВОЗВРАТ

• int: длина самого длинного подмассива, который соответствует критерию

ТО, что я пробовал

 def pickingNumbers(a)
    # Write your code here
    a.sort!
    current_counter = 0
    max_counter = 0
    
    i = 0
    while i < a.size
      j = 1
      
      while (a[j].to_int - a[i].to_int) <= 1
        current_counter  = 1
        j  = 1
        max_counter = current_counter if current_counter > max_counter
      end
      
      i =1
    end
    max_counter
end

input = [1,1,2,2,4,4,5,5,5]
pickingNumbers(input)
 

Запрошенный:

Почему приведенный выше код не сработал? Я был бы признателен, если кто-нибудь сможет объяснить. Я учусь решать алгоритмические задачи и знаю, что есть десятки лучших решений. Тем не менее, я хотел бы знать, почему именно этот код не работает!)) Заранее спасибо

Вы проверяете, чтобы убедиться i < a.size , но вы не делаете то же самое для j .

В конечном итоге вы увеличиваете j за пределы размера массива и пытаетесь получить доступ a[9] , который возвращает nil.

nil.to_int вызывает ошибку (хотя на самом деле вы не указали, какую ошибку вы видели в своем вопросе).

Более идиоматичным способом перебора массива в Ruby является использование .each , которое позволяет избежать этого класса ошибок.

Я бы также не советовал использовать .sort! параметр, который вы передали. Оператор ! bang в конце предупреждает вас, что это изменяет исходный массив.

Вот способ решить ее с большей временной сложностью, который позволяет избежать использования 2 циклов

Я знаю, что можно внести несколько изменений (например, с помощью троичного оператора и так далее). Вы можете цементировать, если у вас есть что-то на уме

 def pickingNumbers(a)
    # Write your code here
    a.sort!
    current_counter = 1
    max_counter = 0
    reference_checker = a[0]
    
    i = 1
    while i < a.size
    
      if (a[i] - reference_checker) <= 1
        current_counter  = 1
      else
        reference_checker = a[i]
        max_counter = current_counter if current_counter > max_counter
        current_counter = 1
      end
      
      i =1
    end
    if current_counter < max_counter
      max_counter
    else
      current_counter
    end
end

input = [1,1,2,2,4,4,5,5,5]
p pickingNumbers(input)
 

Спасибо моей команде поддержки)

Вот два способа решения проблемы: один легко кодируется, другой сложнее, но я ожидаю, что он должен быть быстрее, возможно, намного быстрее. Оба используют следующие массивы для демонстрации.

 a1 = [1,1,2,3,4]
a2 = [1,1,2,2,4,4,5,5,5]
a3 = [1,1,3,2,4,4,5,5,7,6,5,6,5,4,3,4,5,7,8]
 

Немного кода, но может быть достаточно быстрым

 def quick_n_dirty(arr)
  arr.size.downto(1).each do |n|
    arr.each_index.each_cons(n) do |a|
      mn, mx = a.map { |i| arr[i] }.minmax
      return { start: a.first, end: a.last } if mx <= mn   1
    end
  end
end
 

 quick_n_dirty(a1)
  #=> {:start=>0, :end=>2}
quick_n_dirty(a2)
  #=> {:start=>4, :end=>8}
quick_n_dirty(a3)
  #=> {:start=>4, :end=>7}
 

Смотрите Перечислимые #each_cons.

Рассмотрим a1 , который содержит пять элементов. Сначала посмотрите, соответствует ли весь массив требованиям, и в этом случае мы закончили бы:

 enum = a1.each_cons(5)
  #=> #<Enumerator: [1, 1, 2, 3, 4]:each_cons(5)>
 

Чтобы увидеть элементы, которые будут сгенерированы, enum мы можем преобразовать их в массив:

 enum.to_a
  #=> [[1, 1, 2, 3, 4]]
 

Он генерирует только один элемент, a1 сам:

 a = enum.next
  #=> [1, 1, 2, 3, 4]
b, c = a.minmax 
  #=> [1, 4]
 

Как (c-b).abs = 3 и 3 > 1 мы видим, a1 это не соответствует требованиям. Теперь рассмотрим все подмассивы размера 4 . Если найдено одно из них, обладающее желаемым свойством, мы закончили.

 enum = a1.each_cons(4)
  #=> #<Enumerator: [1, 1, 2, 3, 4]:each_cons(4)>
enum.to_a
  #=> [[1, 1, 2, 3], [1, 2, 3, 4]]
a = enum.map { |arr| arr.minmax }
  #=> [[1, 3], [1, 4]]
b = a.map { |x,y| (y-x).abs }
  #=> [2, 3]
b.find { |diff| diff <= 1 }
   #=> nil
 

Это говорит нам о том, что нет подмассива размера 4 , соответствующего требованию, поэтому мы продолжаем рассматривать подмассивы размера 3 :

 enum = a1.each_cons(3)
  #=> #<Enumerator: [1, 1, 2, 3, 4]:each_cons(3)>
enum.to_a
  #=> [1, 1, 2], [1, 2, 3], [2, 3, 4]]
a = enum.map { |arr| arr.minmax }
  #=> [[1, 2], [1, 3], [2, 4]]
b = a.map { |x,y| (y-x).abs }
  #=> [1, 2, 2]
b.find { |diff| diff <= 1 }
  #=> 1
 

Плати грязью! Мы находим, что подмассив [1, 1, 2] соответствует требованию, поэтому мы закончили!

Это то, что делает мой код, за исключением того, что он возвращает хэш, показывающий начало и конец (или я должен сказать «a», а не «the», поскольку могут быть связи) наибольшего подмассива с желаемым свойством. (При повторном прочтении вопроса выясняется, что требуется только длина самого большого подмассива, что допускает незначительное упрощение.)

Если n = arr.size , в худшем случае, количество подмассивов, которые должны быть проверены, равно n (n-1) (n-2) ... 2 1 , что равно n*(n 1)/2 .

Больше кода, но он должен быть быстрее

 def should_be_faster(arr)
  a = arr   [Float::INFINITY]
  current = { early: 0, late: nil }
  a.each_with_index.with_object({ start: 0, end: 0 }) do |(n,i), longest|
    next if i.zero?               
    curr_val = a[i]
    curr_early_val = a[current[:early]]
    curr_late_val = current[:late].nil? ? nil : a[current[:late]]
    if current[:late].nil?
      case curr_val - curr_early_val
      when 0
      when 1, -1
        current[:late] = i
      else
        update_if_improvement(current, longest, i)
        current[:early] = i
        current[:late] = nil
      end
    elsif curr_val != curr_early_val amp;amp; curr_val != curr_late_val
      update_if_improvement(current, longest, i)
      if (curr_val - curr_late_val).abs == 1
        current[:early] = current[:late]
        current[:late] = i
      else
        current[:early] = i
        current[:late] = nil
      end
    end
  end
end
 

 def update_if_improvement(current, longest, i)
  if i - current[:early] > longest[:end] - longest[:start]   1
    longest[:start] = current[:early]
    longest[:end] = i-1
  end
end
 

 should_be_faster(a1)
  #=> {:start=>0, :end=>2}
should_be_faster(a2)
  #=> {:start=>4, :end=>8}
should_be_faster(a3)
  #=> {:start=>4, :end=>7}
 

У меня есть процедура, которая разделит массив на группы, так что [1,1,1,2,2,2,3,3,3] будет 2 массива [1,1,1,2,2,2] и [3,3,3]

очевидно, что если это было для hackerrank, вам нужно посмотреть, достаточно ли это быстро.

если вы хотите ужасный однострочник:

 a.sort.inject({}) {|x,y| x.key?(y-1) ? x[y-1] << y : (x[y]||=[] ; x[y] << y) ; x}.values.map(amp;:count).max
 

или как более длительная процедура:

 def pickingNumbers(a)
  # sort the array and work through the array with an accumulator
  newh = a.sort.each_with_object({}) do |value, acc|
    # check if we had a previous value
    if acc.key?(value - 1)
      # push the current value into the array for the previous value
      acc[value - 1] << value
    else
      # make sure that the "acc[value]" is an array
      acc[value] ||= []
      # push the current value into the value for the current value
      acc[value] << value
    end
  end

  # get the size of all of the values in the newly created hash
  vals = newh.values.map(amp;:count)

  # return the maximum of that array
  vals.max
end

input = [1,1,2,2,4,4,5,5,5]
pickingNumbers(input)