找到 N 个数字中缺少的数字

题意如题找到 N 个数字中缺少的一个数字

方法 1:求和

　　　算出 1 + 2 + ... + N 的和然后减去数组中 N - 1 个数字的和

int missNum(int N, int a[maxn]) {
    long long sum = 0;
    for(int i = 0; i < N - 1; i ++)
        sum += a[i];

    return (1 + N) * N / 2 - sum;
}

　　这个方法的缺点是有可能会出现溢出时间复杂度是 O(N)

方法2:位运算

　　　用与运算 a ^ a = 0 a ^ a ^ b = b 所以可以用位运算实现

int missNum(int N, int a[maxn]) {
    int ans = N;

    for(int i = 0; i < N - 1; i ++)
        ans ^= (a[i] ^ (i + 1));

    return ans;
}

　　时间复杂度 O(N)

方法3:二分法

　　　如果无序数组要先排序在此假设数组有序

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
int N;
int a[maxn];

int main() {
    scanf("%d", &N);
    for(int i = 0; i < N - 1; i ++)
        scanf("%d", &a[i]);

    int l = 0, r = N - 1, mid;
    while(l <= r) {
        mid = (l + r) / 2;
        if(a[mid] == mid + 1) l = mid +1;
        else r = mid - 1;
    }

    printf("%d\n", mid + 1);

    return 0;
}

原文链接: https://www.cnblogs.com/zlrrrr/p/13271816.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/364219

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

找到 N 个数字中缺少的数字

相关推荐