subject ：
A length of n−1 All numbers in the array of are unique , And every number is in the range 0 To n−1 within .
In scope 0 To n−1 Of n There are and only one number is not in the array , Please find out the number .
in addition ：leetcode： This array is not a sorted array ; Sword finger book ： Incrementally sorted array .
Code ：
class Solution:
def math(self , nums): # Method 1： Mathematical way , Whether sorted or not
n = len(nums)
expected_sum = n*(n +1) // 2
actual_sum = sum(nums)
return expected_sum - actual_sum
def sword_offer_sorted(self , nums): # Method 2： For sorted arrays , Two points
i , j = 0 , len(nums) - 1
while i < j:
mid = (i + j ) // 2
half_num = (nums[i] + nums[j]) // 2
if nums[mid] > half_num:
j = mid
else:
i = mid + 1
return i
def leetcode_no_sorted(self , nums): # Method 3： Unordered array , Prioritize , In use method 2
nums = sorted(nums)
self.sword_offer_sorted(nums)
