Целые числа в массиве либо совершенно нечетные, либо полностью четные, за исключением одного целого числа - PullRequest
0 голосов
/ 07 марта 2019

Вам дан массив (который будет иметь длину не менее трех, но может быть очень большим), содержащий целые числа.Массив либо целиком состоит из нечетных целых чисел, либо целиком состоит из четных целых чисел, за исключением одного целого числа N. Напишите метод, который принимает массив в качестве аргумента и возвращает этот выброс N.

Это мой код, который, кажется, не работает:

arr = [160, 3, 1719, 19, 11, 13, -21]
n = arr.length

def getOddOccurrence(arr, arr_size)
  for i in range(0, arr_size)
    count = 0
    for j in range(0, arr_size)
      if arr[i] == arr[j]
        count += 1
      end
      if(count % 2 != 0)
        return arr[i]
      end
    end
  end
  return -1
end

print getOddOccurrence(arr, n)

Какие изменения мне нужны с этим кодом?

Ответы [ 4 ]

2 голосов
/ 08 марта 2019

Вот решение, которое является загадочным (некрасивым), но относительно простым. Это занимает O (arr.size) времени и использует O (1) дополнительное хранилище. Это также "короткое замыкание", как только оно находит выброс.

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

def getOddOccurrence(arr)
  arr.each_index do |i|
    return arr[i == 1 && (arr[i] ^ arr[i + 1]) & 1 == 0 ? 0 : i] if i > 0 && (arr[i] ^ arr[i - 1]) & 1 == 1
  end
end

А вот та же концепция в несколько более рубиновой манере:

def getOddOccurrence(arr)
  arr.each_cons(3) { |x,y,z| return ((y ^ z) & 1 == 1 ? y : x) if (x ^ y) & 1 == 1 }
  arr[-1]
end

Если вы предпочитаете смотреть на подмножества 2, выполните однократную проверку первых 3 значений, а затем работайте с cons(2) подмножествами. Вы также можете заменить битовое тестирование проверкой согласованности на четность (или нечетность) для улучшения читабельности:

def getOddOccurrence(arr)
  return arr[0] if (arr[0].odd? ^ arr[1].odd?) && !(arr[1].odd? ^ arr[2].odd?)
  arr.each_cons(2) { |x,y| return y if (x.odd? ^ y.odd?)}
end

Наконец-то у меня появилось несколько свободных минут, чтобы собрать тест:

require 'benchmark/ips'

def getOddOccurrence_cons3(arr)
  arr.each_cons(3) { |x,y,z| return ((y ^ z) & 1 == 1 ? y : x) if (x ^ y) & 1 == 1 }
  arr[-1]
end

def getOddOccurrence_cons2(arr)
  return arr[0] if (arr[0].odd? ^ arr[1].odd?) && !(arr[1].odd? ^ arr[2].odd?)
  arr.each_cons(2) { |x,y| return y if (x.odd? ^ y.odd?) }
end

def getOddOccurrence_cons2_bits(arr)
  return arr[0] if ((arr[0] ^ arr[1]) & 1 == 1) && ((arr[1] ^ arr[2]) & 1 == 0)
  arr.each_cons(2) { |x,y| return y if (x ^ y) & 1 == 1 }
end

def getOddOccurrence_find(arr)
  arr.first(3).count(&:odd?) > 1 ? arr.find(&:even?) : arr.find(&:odd?)
end

def getOddOccurrence_find_bits(arr)
  arr.first(3).sum {|x| x & 1} > 1 ? arr.find { |x| (x & 1) == 0 } : arr.find { |x| (x & 1) == 1 }
end

def find_outlier(ary)
  # fetch first 3 numbers and determine what kind of array
  # are we dealing with here, mostly odd or mostly even?
  mostly_odd = ary.take(3).count(&:odd?) > 1

  # then just go and find the outlier element
  if mostly_odd
    ary.find(&:even?)
  else
    ary.find(&:odd?)
  end
end

arr = Array.new(10_000) { |i| i * 2 }.shuffle << 5

Benchmark.ips do |b|
  b.report('cons3 bits:') { getOddOccurrence_cons3(arr) }
  b.report('cons2 bits:') { getOddOccurrence_cons2_bits(arr) }
  b.report('cons2 even/odd:') { getOddOccurrence_cons2(arr) }
  b.report('find even/odd:') { getOddOccurrence_find(arr) }
  b.report('find bits:') { getOddOccurrence_find_bits(arr) }
  b.report('find sergio:') { find_outlier(arr) }
  b.compare!
end

Как видите, я поместил нечетное значение в конец четного массива, чтобы максимально увеличить требуемый поиск.

И победитель ...

Warming up --------------------------------------
         cons3 bits:   128.000  i/100ms
         cons2 bits:   127.000  i/100ms
     cons2 even/odd:   103.000  i/100ms
      find even/odd:   216.000  i/100ms
          find bits:   217.000  i/100ms
        find sergio:   231.000  i/100ms
Calculating -------------------------------------
         cons3 bits:      1.251k (± 4.9%) i/s -      6.272k in   5.026355s
         cons2 bits:      1.294k (± 3.4%) i/s -      6.477k in   5.010802s
     cons2 even/odd:      1.038k (± 4.4%) i/s -      5.253k in   5.070617s
      find even/odd:      2.284k (± 4.2%) i/s -     11.448k in   5.022831s
          find bits:      2.165k (± 5.3%) i/s -     10.850k in   5.027801s
        find sergio:      2.277k (± 3.3%) i/s -     11.550k in   5.078381s

Comparison:
      find even/odd::     2283.6 i/s
        find sergio::     2276.9 i/s - same-ish: difference falls within error
          find bits::     2164.6 i/s - same-ish: difference falls within error
         cons2 bits::     1294.2 i/s - 1.76x  slower
         cons3 bits::     1251.1 i/s - 1.83x  slower
     cons2 even/odd::     1038.1 i/s - 2.20x  slower

... строчка из комментария Сагар Пандьяр!

Подход, основанный на find, явно превосходит each_cons. Использование методов Ruby odd / even против бинарных операций, по-видимому, оказывает лишь незначительное влияние. Интересно, что использование .each_cons(3) вместо .each_cons(2) также имеет очень небольшое относительное влияние, хотя в обоих подходах явно доминирует подход Сагар и Серджио.

1 голос
/ 08 марта 2019

Добро пожаловать в переполнение стека!

Поскольку вы новичок, позвольте мне начать с того, что просьба о решениях здесь обычно не принимается хорошо. Это не место, чтобы другие люди делали вашу работу за вас, поэтому вы должны проверить https://stackoverflow.com/help/how-to-ask, чтобы узнать, что является хорошим вопросом для будущего.

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

if arr[i] == arr[j]
  count +=1
end

Приведенный выше код ищет два числа в массиве, которые равны. Это означает, что count никогда не будет увеличиваться, если в вашем массиве нет двух одинаковых значений, что не соответствует описанию задачи. Кроме того, эта проблема действительно не требует сравнения двух чисел в массиве. Вам просто нужно определить, является ли каждое число нечетным или четным, и найти выброс.

Самым простым (и, возможно, наиболее распространенным) способом программирования определения нечетного числа является использование оператора по модулю (%). Вы использовали это при проверке переменной count, что опять же не совсем то, что вам нужно. Вместо этого вы должны использовать его против каждой записи в массиве. Таким образом, для некоторого целого значения n, n % 2 будет 0, если это четное число, или 1, если это нечетное число. Похоже, что вы в некоторой степени это поняли, но используйте это для каждого числа в массиве, чтобы определить, является ли оно четным или нечетным, вместо переменной count, и затем вы можете воздействовать на эту информацию для каждого числа.

Как только вы получите его, чтобы определить, является ли каждое число в массиве четным или нечетным, вам нужен способ отследить, ищете ли вы нечетное или четное число. Самый простой способ сделать это - отслеживать четное / нечетное количество в переменной, но иметь одну переменную для четного и отдельную для нечетного. Поэтому, когда вы сталкиваетесь с четным числом, вы можете добавить 1 к четному числу, и аналогично для нечетных чисел, но к нечетному числу. Таким образом, вы узнаете, что тип, который вы ищете (четный или нечетный), будет равным 1 после того, как вы закончите проходить массив. Это означает, что эти переменные должны находиться вне цикла, который просматривает массив, так как вы не хотите, чтобы они сбрасывались для каждого числа в массиве, и вы, вероятно, захотите посмотреть их и после цикла.

Как только вы определили, ищете ли вы нечетный или четный, вы можете пройти через массив второй раз (не вложенный цикл, а второй после первого) и вернуть нечетное или четное число из массив в зависимости от обстоятельств. Есть способы сделать это без второго цикла, но я пытаюсь сделать это прямо вперед.

Надеюсь, это поможет вам найти собственное решение, чтобы вы могли учиться на решении проблемы. Если вы работаете с моим основным макетом, есть несколько способов улучшить его с точки зрения производительности или просто объема кода (например, без использования второго цикла). Рад уточнить, если вам нужно.

Удачного кодирования!

1 голос
/ 08 марта 2019

Вот алгоритм постоянной памяти с линейным временем

def find_outlier(ary)
  # fetch first 3 numbers and determine what kind of array
  # are we dealing with here, mostly odd or mostly even?
  mostly_odd = ary.take(3).count(&:odd?) > 1

  # then just go and find the outlier element
  if mostly_odd
    ary.find(&:even?)
  else
    ary.find(&:odd?)
  end
end

ary = [161, 3, 1719, 19, 11, 160, 13, -21]

find_outlier(ary) # => 160
1 голос
/ 07 марта 2019

Вот простой способ сделать это

arr = [160, 3, 1719, 19, 11, 13, -21]
arr.group_by(&:odd?).values.sort_by(&:count)[0][0]
# => 160

group_by(&:odd?) Создает 2 хэша для нечетных и четных чисел

values Будет захватывать значения хэша.2 массива, для четных и нечетных

sort_by(&:count) Сортировать массивы, один с меньшими значениями будет первым

[0][0] Захватить первый номер первого массива

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...