当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.268.Missing Number 连续数组中缺失的数

LeetCode.268.Missing Number 连续数组中缺失的数

题目描述

268 Missing Number
https://leetcode-cn.com/problems/missing-number/

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?


解题过程

第一想法是求和 sum(1…n) = n(n+1)/2 再减去数组和,但可能有溢出的风险。
看题解知道可以用异或,时间复杂度 O(n),空间复杂度 O(n)

private static class SolutionV2020 {
    public int missingNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
           res ^= nums[i];
           res ^= i+1;
        }
        return res;
    }
}

GitHub代码

leetcode-java/problems/_268_MissingNumber.java
https://github.com/masikkk/leetcode-java/blob/master/problems/_268_MissingNumber.java


上一篇 LeetCode.137.Single Number II 数组中只出现一次的数2

下一篇 LeetCode.169.Majority Element 数组的众数/主元素

阅读
评论
181
阅读预计1分钟
创建日期 2020-02-11
修改日期 2020-02-11
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论