如何在数组中找到唯一编号，而 return 仅在 ruby 中找到该编号？

Question

有一个包含一些数字的数组。除一外，所有数字都相等。我正在尝试获得这种类型的东西：

find_uniq([ 1, 1, 1, 2, 1, 1 ]) == 2

find_uniq([ 0, 0, 0.55, 0, 0 ]) == 0.55

我试过这个：

def find_uniq(arr)
   arr.uniq.each{|e| arr.count(e)}
end

它为我提供了数组中的两个不同值，但我不确定如何选择唯一的值。我可以使用某种计数吗？谢谢！

这有效：

def find_uniq(arr)
  return nil if arr.size < 3
  if arr[0] != arr[1]
    return arr[1] == arr[2] ? arr[0] : arr[1]
  end
  arr.each_cons(2) { |x, y| return y if y != x }
end

感谢 pjs 和 Cary Swoveland。

Answer 1

我会这样做：

[ 1, 1, 1, 2, 1, 1 ]
  .tally                    # { 1=>5, 2=>1 }
  .find { |_, v| v == 1 }   # [2, 1]
  .first                    # 2

或如 3limin4t0r 所建议：

[ 1, 1, 1, 2, 1, 1 ]
  .tally                    # { 1=>5, 2=>1 }
  .invert[1]                # { 5=>1, 1=>2 } => 2

Answer 2

您的代码可以通过使用 find 而不是 each 来修复：

def find_uniq(arr)
  arr.uniq.find { |e| arr.count(e) == 1 }
end

然而，这是非常低效的，因为 uniq 需要迭代整个集合。找到唯一值后，arr 集合被 count 迭代 1 或 2 次（假设只有两个唯一值），具体取决于值在 uniq 结果中的位置.

对于简单的解决方案，我建议查看，它只迭代整个集合一次。

对于您的特定场景，您可以通过使计数器短路来从技术上提高性能。如果计数包含 2 个不同的值并且至少计数了 3 个项目，则通过手动计数和中断循环来完成。

def find_uniq(arr)
  tally = Hash.new(0)
  arr.each_with_index do |item, index|
    break if tally.size == 2 && index >= 3
    tally[item] += 1
  end
  tally.invert[1]
end

Answer 3

以下内容不使用计数，并且会在找到唯一项目时缩短搜索。首先，它 returns nil 如果数组的元素少于 3 个，因为在这种情况下无法回答问题。如果该检查通过，它将通过比较相邻值来工作。它会预先检查前两个元素是否相等——如果不相等，它会检查第三个元素以确定哪个不同。否则，它遍历数组和 returns 它找到的第一个不相等的值。它 returns nil 如果数组中没有可区分的元素。

def find_uniq(arr)
  return nil if arr.size < 3
  if arr[0] == arr[1]
    arr.each.with_index do |x, i|
      i += 1
      return arr[i] if arr[i] != x
    end
  elsif arr[1] == arr[2]
    arr[0]
  else
    arr[1]
  end
end

这也适用于非数字数组，例如 find_uniq(%w(c c c d c c c c))。

感谢 Cary Swoveland 提醒我 each_cons。这可以大大加强解决方案：

def find_uniq(arr)
  return nil if arr.size < 3
  if arr[0] != arr[1]
    return arr[1] == arr[2] ? arr[0] : arr[1]
  end
  arr.each_cons(2) { |x, y| return y if y != x }
end

Answer 4

对于除小型数组以外的所有数组，此方法有效地具有 Enumerable#find.

的速度

def find_uniq(arr)
  multi = arr[0,3].partition { |e| e == arr.first }
                  .sort_by { |e| -e.size }.first.first
  arr.find { |e| e != multi }
end

find_uniq [1, 1, 1, 2, 1, 1]       #=> 2
find_uniq [0, 0, 0.55, 0, 0]       #=> 0.55
find_uniq [:pig, :pig, :cow, :pig] #=> :cow

问题的措辞暗示数组至少包含三个元素。它当然不能为空或有两个元素。（如果它可以包含一个元素，请添加保护子句 return arr.first if arr.size == 1。）

我检查前三个元素以确定具有重复项的对象，我将其分配给变量 multi。然后我就可以使用 find。 find 相当快，部分原因是它短路（在达到匹配时停止枚举数组）。

如果

arr = [1, 1, 1, 2, 1, 1]

然后

a = arr[0,3].partition { |e| e == arr.first }.sort_by { |e| -e.size }
  #=> [[1, 1, 1], []]
multi = a.first.first
  #=> 1

如果有以下任何一项：

arr = [2, 1, 1, 1, 1, 1]
arr = [1, 2, 1, 1, 1, 1]
arr = [1, 1, 2, 1, 1, 1]

然后申请

a = arr[0,3].partition { |e| e == arr.first }.sort_by { |e| -e.size }
  #=> [[1, 1], [2]]
multi = a.first.first
  #=> 1

让我们比较一下已提供的解决方案的计算性能。

def spickermann1(arr)
  arr.tally.find { |_, v| v == 1 }.first
end

def spickermann2(arr)
  arr.tally.invert[1]
end

def spickermann3(arr)
  arr.tally.min_by(&:last).first
end

def pjs(arr)
  if arr[0] == arr[1]
    arr.each.with_index do |x, i|
      i += 1
      return arr[i] if arr[i] != x
    end
  elsif arr[1] == arr[2]
    arr[0]
  else
    arr[1]
  end
end

我没有包括@3limin4t0r 的解决方案，因为作者承认它相对低效。但是，我确实包括了@spikermann 答案的两个变体，一个（“spickermann2”）是由@3limin4t0r 在评论中提出的。

require 'benchmark'

def test(n)
  puts "\nArray size = #{n}"
  arr = Array.new(n-1,0) << 1
  Benchmark.bm do |x|
    x.report("Cary")         { find_uniq(arr) }
    x.report("spickermann1") { spickermann1(arr) }
    x.report("spickermann2") { spickermann2(arr) }
    x.report("spickermann3") { spickermann3(arr) }
    x.report("PJS")          { pjs(arr) }
  end
end

test 100
Array size = 100
                 user     system      total        real
Cary          0.000032   0.000009   0.000041 (  0.000029)
spickermann1  0.000022   0.000015   0.000037 (  0.000019)
spickermann2  0.000017   0.000002   0.000019 (  0.000016)
spickermann3  0.000019   0.000002   0.000021 (  0.000018)
PJS           0.000042   0.000025   0.000067 (  0.000034)

test 10_000
Array size = 10_000
                 user     system      total        real
Cary          0.001101   0.000091   0.001192 (  0.001119)
spickermann1  0.000699   0.000096   0.000795 (  0.000716)
spickermann2  0.000794   0.000071   0.000865 (  0.000896)
spickermann3  0.000776   0.000081   0.000857 (  0.000781)
PJS           0.001140   0.000113   0.001253 (  0.001300)

test 1_000_000
Array size = 1_000_000
                 user     system      total        real
Cary          0.061148   0.000787   0.061935 (  0.063022)
spickermann1  0.043598   0.000474   0.044072 (  0.044590)
spickermann2  0.044909   0.000663   0.045572 (  0.046371)
spickermann3  0.042907   0.000210   0.043117 (  0.043162)
PJS           0.072766   0.000226   0.072992 (  0.073168)

我将@spickermann 的回答的明显优势归因于 Enumerable#tally 没有要评估的块（例如，与我的回答中的 Enumerable#find 不同).

如何在数组中找到唯一编号，而 return 仅在 ruby 中找到该编号？

How do I find the unique number in an array and return only that number in ruby?

ruby

arrays

methods

unique