Find the Missing Number-蒲公英云

Find the Missing Number

青旅半醒 2021-12-16 07:25 318阅读 0赞

方法一：数学方法，先找到最大的值，需要比较最大的值和array size，要是比array size小，说明最大值missing。然后用等差数列公式求得如果不缺失值的和，然后再减去array里数的和。

class Solution {
public:
    /**    
     * @param nums: a vector of integers
     * @return: an integer
     */
    int findMissing(vector<int> &nums) {
        // write your code here
        int max = 0;
        int sum = 0;
        for (int i : nums){
            if(i > max) max = i;
            sum += i;
        }
        int calmax = max == nums.size()? max : max + 1;
        int calsum = calmax * (nums.size()+1) /2 ;
        return calsum - sum;
    }
};

方法二：

先把不缺失的所有数取xor，然后再对数组里的数取xor，剩下的就是最后的结果。

public class Solution {
    /**    
     * @param nums: an array of integers
     * @return: an integer
     */
    public int findMissing(int[] nums) {
        // write your code here
        int result = 0;
        for (int i = 0; i <= nums.length; i++){
            result ^= i;
        }
        for(int i = 0; i < nums.length; i++){
            result ^= nums[i];
        }
        return result;
    }
}