Skip to content

Latest commit

 

History

History
195 lines (171 loc) · 5 KB

README.md

File metadata and controls

195 lines (171 loc) · 5 KB

题目描述: 缺失数字

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

说明 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [3,0,1]
输出: 2

示例 2:

输入: [9,6,4,2,3,5,7,0,1]
输出: 8

解题思路:

方法一：利用哈希表来做，unordered_map<int,int> map,map[nums[i]]==1。

方法二：数学方法，相减，0-n相加再减去nums数组所有元素之和。异或：res = nums.size()，res与nums中的元素异或，在与i异或，如果nums[i]和i都存在，则异或为0，缺失的数字就与i相对应，异或满足交换律。

方法三：排序法，将数组按顺序排序，数组元素与与相对应下标是否相等，若不相等则返回相应的下标，即为缺失数字。

时间复杂度：

方法一： O(n)

方法二： O(n)

方法三： O(nlogn)

空间复杂度

方法一：O(n)

方法二：O(1)

方法三：空间复杂度取决于使用的排序算法，根据排序算法是否进行原地排序（即不使用额外的数组进行临时存储），空间复杂度为 O(1) 或 O(n)。

代码

C++:

方法一： 哈希表(unordered_map) 基于哈希表 ，map基于红黑二叉树

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res =0;
        int n = nums.size();
        unordered_map<int,int> map;
        for (int i=0;i<n;i++)
        {
            map[nums[i]]++;
        }
        for (int i=0;i<=n;i++)
        {
            if (map[i] == 0)
            {
                res = i;
                break;
            }
        }
        return res;
    }
};

方法二： 数学方法(0-n相加再减去nums数组所有元素之和)

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res =0;
        int n = nums.size();
        int sum_num = 0;
        int Sum = 0;
        for (int i=0;i<n;i++)
        {
            sum_num+=nums[i];
        }
        for (int i=0;i<=n;i++)
        {
            Sum += i;
        }
        res = Sum - sum_num;
        return res;
    }
};

方法二： 数学方法(异或)(重要)

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int res = n;  
        // res 设为n的原因，
        // 1）所有数字出现两次，XOR将使它归零。
        // 2）下标i是从0～nums.size()-1的，而数字是从0~nums.size()的（缺了一个）。
        // 3）你需要将初始值，设置为下标不能达到的那个值。
        for (int i = 0; i < n; i++)
        {
            res ^= nums[i];
            res ^= i;
            // 异或满足交换律，i和nums[i]是肯定有重复的，剩下的只有一个那就是nums中缺失的
        }
        return res;
    }
};

方法三： 排序

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int n = nums.size();
        int res = 0;
        if (nums[n-1]!=n)
        {
            return n;
        }
        for (int i=0;i<n;i++)
        {
            if (nums[i]!=i)
            {
                res = i;
                break;
            }
        }
        return res;
    }
};

Python:

方法一：哈希表

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        res = 0
        n = len(nums)
        nums_set = set(nums)
        for num in range(n+1):
            if num not in nums_set:
                return num
        return res

方法二 ：数学方法

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        res = 0;
        n = len(nums)
        x = range(n+1)
        x = list(x)           ### Python3 需要用list转换成数组
        res = sum(x)-sum(nums)
        return res

方法二 ：数学方法(异或)

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        res = n
        for i in range(n):
            res = res ^ nums[i]
            res = res ^ i
        return res

方法三：排序法

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        nums = sorted(nums)
        n = len(nums)
        if nums[-1] != n:
            return n
        for i in range(0,n):
            if i!=nums[i]:
                return i

参考