LeetCode268. Missing Number解题

雨点打透心脏的1/2处 2022-06-05 05:35 194阅读 0赞

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

For example,  
Given nums = \[0, 1, 3\] return 2.

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

Credits:  
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

> 题目的大意是：给你一个数组，里面的元素是从0，1，2，……n这n+1个数字中取出n个来构成的，也就意味着有一个数字是缺失的，你要找到这个数字  
> 题目有个特别要求：你要在O(n)时间复杂度内解决这个问题，并且只能用O(1)的空间复杂度。有的同学就会问这个O(1)的空间复杂度，也就是常量额外空间复杂度是什么，这个就是说你的额外空间必须是常量个，不能跟问题的规模n相关，你可以设置1个int变量也可以设置100个int变量，但是不能用一个长度为跟输入数组长度一样的int数组

# 分析 #

既然数组里的元素是从0到n无重复的取，那就用等差数列来算，先算出给定数组所有的数的和，再跟0到n的等差数列的和相比，差的值就是缺失的数字。

class Solution {
    public:
        int missingNumber(vector<int>& nums) {
            int i;
            int sum=0;
            int stdSum;
            int size;
    
            size=nums.size();
    
            //count sum
            for(i=0;i<size;i++){
                sum+=nums[i];
            }
            //count the standard sum
            if(size%2){
       //odd
                stdSum=(size/2+1)+((size-1)*(size+1))/2;
            }else{
       //even
                stdSum=(size/2)*(size+1);
            }
    
            return stdSum-sum;
        }
    };

# 更好的算法 #

这个我一时还看不懂，有懂的同学欢迎留言分享

public int missingNumber(int[] nums) {
    
            int rt = nums.length;
    
            for (int i = 0; i < nums.length; i++) {
                rt = rt ^ nums[i] ^ i;
            }
    
            return rt;
        }

\*来自[leetCode 268 Missing Number @\_我们的存在][leetCode 268 Missing Number]

[leetCode 268 Missing Number]: http://blog.csdn.net/yano_nankai/article/details/50273611