Number Zoo Patrol
Number Zoo Patrol
问题描述
Background:
作者：housz77
You’re working in a number zoo, and it seems that one of the numbers has gone missing!
Zoo workers have no idea what number is missing, and are too incompetent to figure it out, so they’re hiring you to do it for them.
In case the zoo loses another number, they want your program to work regardless of how many numbers there are in total.
Task:Write a function that takes a shuffled list of unique numbers from 1 to n with one element missing (which can be any number including n). Return this missing number.
Note: huge lists will be tested.
Examples:[1, 3, 4] => 2
[1, 2, 3] => 4
[4, 2, 3] => 1
首先想到，先对给定的list排序，然后遍历所有的元素，将元素与索引+1作比较，发现 time out，傻傻的做法，有待改进
python代码如下def find_missing_number(numbers):
numbers.sort()
for i, num in enumerate(numbers):
if not (i+1==num):
return i+1
return i+2
解法2
想到类似于折半查找的方法, 仍然time out
python代码如下：def find_missing_number(numbers):
numbers.sort()
len_num = len(numbers)
lack_num = len_num+1
left_ptr = 0
right_ptr = len_num-1
while left_ptr mid_ptr+1:
if (mid_ptr+1<lack_num):
lack_num = mid_ptr+1
right_ptr = mid_ptr - 1
return lack_num
解法3
根本看不懂的思路，但是轻松通过
def find_missing_number(numbers):
len_num = len(numbers)
return int((len_num+2)*(len_num+1)/2 - sum(numbers))
作者：housz77
