找出连续数组0-N中欠缺的数

// 1.给出一个x=0，x先跟0-n的每个数字异或，再跟数组里的每个值异或，留下来的则是欠缺的数字。时间复杂度O(N)

int missnumbers(int arr[],int number)
{
    int x = 0;
    for (int i = 0; i <=number; i++)
    {
        x ^= i;
    }
    for (int i = 0; i < number; i++)
    {
        x ^= arr[i];
    }
    return x;
}
int main()
{
    int arr[] = { 3,0,1 };
    printf("%d\n", missnumbers(arr,3));
    return 0;
}

//2.数组中的值是多少就放在第几个位置，再从0-N进行比较。时间复杂度O（N)

#include

#include
int missnumbers(int* p, int number)
{
    
    int* str = (int*)malloc((number+1)*sizeof(int));
    if (str == NULL)
    {
        perror("missnumbers");
        return -1;
    }
    for (int i = 0; i < number; i++)
    {
        *(str+p[i]) = p[i];
    }
    for (int i = 0; i < number; i++)
    {
        if (*str++!=i)
        {
            return i;
        }
    }
    free(str);
    str = NULL;
    return -1;
}
int main()
{
    int arr[] = { 3,0,1,2,5 };
    int count = sizeof(arr) / sizeof(arr[0]);
    printf("%d\n", missnumbers(arr, count));
    return 0;
}
 

//3.从0加到n,再减去数组中所有值的和。时间复杂度O(N)

int missnumbers(int* p, int number)
{
    int sum = 0;
    for (int i = 0; i < number; i++)
    {
        sum += i - p[i];
    }
    return sum + number;
}
int main()
{
    int arr[] = { 3,0,1 };
    int count = sizeof(arr) / sizeof(arr[0]);
    printf("%d\n", missnumbers(arr, count));
    return 0;
}
 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！