6/4 每日一題

nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

 

Example 1:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

 

Constraints:

• n == nums.length
• 1 <= n <= 104
• 0 <= nums[i] <= n
• All the numbers of nums are unique.

class Solution:

    def missingNumber(self, nums: List[int]) -> int:

        nums_set=set()

        for i in nums:

            nums_set.add(i)

        for i in range(len(nums)):

            if i not in nums_set:

                return i  #找到缺失的值

        return len(nums) #通過迴圈就必定是最後一位

----------參考解答 0+1+..+n 在減掉nums的總和就是缺失的數字

class Solution:

    def missingNumber(self, nums: List[int]) -> int:

        n = len(nums)

        ideal_sum = (n * (n + 1)) // 2  # 理想總和

        actual_sum = sum(nums)  # nums中所有數字的總和

        return ideal_sum - actual_sum  # 差值即為缺失的數字

-------------XOR運算 (兩兩相同會變成0)

class Solution:

    def missingNumber(self, nums: List[int]) -> int:

        '''先對範圍從0-N的數字進行XOR運算,得到一個missing_num,

           然後對nums的每個數字進行XOR運算(兩兩相同會變成0)

           得到的數字就是單獨一個的數字,也就是缺失的值

         '''

        n = len(nums)

        missing_num = 0

       

       

        for i in range(n + 1):

            missing_num ^= i

       

        # 對數組中的所有數字進行XOR運算

        for num in nums:

            missing_num ^= num

       

        return missing_num