0

Here's the exercise:

You have been given a list of sequential numbers from 1 to 10,000, but they are all out of order; furthermore, a single number is missing from the list. The object of the task is to find out which number is missing.

The strategy to this problem is to sum the elements in the array, then sum the range 1 to 10,000, and subtract the difference. This is equal to the missing number. The formula for calculating the sum of the range from 1..n being n(n+1)/2.

This is my current approach:

def missing_number(array)
  sum = 0
  array.each do |element|
  sum += element
  end

  ((10000*10001)/2) - sum
end

Where I am getting tripped up is the output when I input an array such as this:

puts missing_number(*1..10000) #=> 0

Why does this happen?

Thanks!

4

4 回答 4

3

无需对数组进行排序。一个长度为 N 的数组应该包含除一个数字之外的所有数字1..(N+1)，因此数组长度 + 1 是确定所有值都存在时的 grand_sum 的基础。

def missing_number(array)
  grand_sum = (array.length + 1) * (array.length + 2) / 2
  grand_sum - array.inject(:+)
end

附录

此方法将数组作为参数，而不是范围。您不能直接使用范围，因为不会有缺失值。在调用该方法之前，您需要一些机制来生成满足问题描述的数组。这是一种可能的解决方案：

PROBLEM_SIZE = 10_000
# Create an array corresponding to the range
test_array = (1..PROBLEM_SIZE).to_a
# Target a random value for deletion -- rand(N) generates values in
# the range 0..N-1, inclusive, so add 1 to shift the range to 1..N
target_value = rand(PROBLEM_SIZE) + 1
# Delete the value and print so we can check the algorithm
printf "Deleting %d from the array\n", test_array.delete(target_value)
# Randomize the order of remaining values, as per original problem description
test_array.shuffle!
# See what the missing_number() method identifies as the missing number                     
printf "Algorithm identified %d as the deleted value\n", \
       missing_number(test_array)
于 2013-05-25T23:53:23.400 回答
1

如果它不是性能关键的问题，由于其可读性，另一种解决问题的方法：

def missing_number(array)
  (1..10_000).to_a - array
end
于 2013-05-26T07:31:16.227 回答
0

您不应该使用*1..10000，这只会扩展到 10,000 个参数。将返回零，因为在您需要删除一个(1..10000).to_a之间没有缺少任何元素。下面是一些带有详细解释的代码。 1..10000

def missing_number array
  # put elements in order                                                                
  array.sort!

  # get value of last array element                                                      
  last  = array[-1]

  # compute the expected total of the numbers                                            
  # 1 - last 
  # (n + 1)(n)/2                                                               
  expected = (last + 1) * (last / 2)

  # actual sum                                                                           
  actual = array.inject{|sum,x| sum + x}

  # find missing number by subtracting                                                   
  (expected - actual)
end

test = (1..10000).to_a
test.delete 45
puts "Missing number is: #{missing_number(test)}"
于 2013-05-25T23:38:52.083 回答
0

Instead of *1..10000, the argument should be (1..10000).to_a.

于 2013-05-25T23:32:35.527 回答