LeetCode-268. 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?

分析

思路:
找出最大值,进行判断,看那一位数字缺少。

C语言代码

#include <stdio.h>
int missingNumber(int* nums, int numsSize) {
    int n=numsSize+1;
//    计算出相对应的n
    for(int i=0;i<numsSize;i++)
    {
        if(n<nums[i])
        {
            n=nums[i];
        }
    }
//    求所缺少的数值是那个
    for(int i=0;i<n;i++)
    {
        int flag=0;
        int j=0;
        for(;j<numsSize;j++)
        {
//            若存在 相对应的数值则 flag=1
            if(i==nums[j])
            {
                flag=1;
            }

        }
        if(flag==0&&j==numsSize)
        {
            return i;
        }
    }
    return 0;
}
int main()
{
    int nums[]={0};
    int numsSize= sizeof(nums)/ sizeof(int);
    printf("%d\n",missingNumber(nums,numsSize));
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注