有效地创建一个包含 n 个数字的数组，不包括 k 个给定数字

Question

如何创建一个从 1 开始到 n 结束的数字数组，同时不包括数组中的 k 个给定数字？例如 n=10 k=2 并且 k 值的两个数字是 3 和 6 那么我的数组是 1,2,4,5,7,8,9,10.

我必须对大量数据执行此操作，例如

1 < n < 10^9

然后

0 < k < min(10^5,n)

对于小数字，我尝试建立索引，然后将其存储在另一个数组中，这占用了很多 space 和 time.How 我可以有效地做到这一点吗？

            scanf("%lld%lld",&n,&k);
            f=0;
            long long int a[100010]={0};
            long long int b[100010]={0};
            for(i=0;i<k;i++)
            {
            scanf("%lld",&temp);
            a[temp]=-1;
            }
            for(i=0;i<n+1;i++)
            {
                if(a[i]!=-1)
                {
                b[f++]=i;
                }
            }

Answer 1

使用n作为范围的结束，k作为跳过数字的个数，narr作为保存结果的数组，karr作为包含要跳过的数字的数组：karr 只需要 k 个元素长。如果 karr 已排序，您只需将每个新数字与 karr 中的一个元素进行比较，当它们匹配时移动到下一个 karr 并将新数字添加到 narr当他们不这样做时。以下示例显示了这一点（但没有错误检查）：

#include <stdlib.h> // for malloc and qsort
#include <stdio.h>  // for printf

// compare function for qsort
static int llcompare(const void *a, const void *b)
{
    if (*(long long *)a > *(long long *)b) return 1;
    if (*(long long *)b < *(long long *)b) return -1;
    return 0;
}

int main()
{
    long long n = 0, k = 0;
    scanf("%lld%lld",&n,&k); // get n and k, as in your code

    // allocate arrays: k elements for karr, and (n - k) for results in narr
    long long *karr = malloc(sizeof(long long) * k);
    long long *narr = malloc(sizeof(long long) * (n - k));

    // read numbers to skip into karr
    for (int i = 0; i < k; i++) {
        scanf("%lld", &karr[i]);
    }
    // sort karr ascending
    qsort(karr,k,sizeof(long long),llcompare);

    // using pointers to move through narr and karr
    long long *pn = narr; // element of narr to set
    long long *pk = karr; // element of karr to compare against

    // pkend marks the end of karr, to check when we've passed the last omitted
    // number
    long long *pkend = karr + k;

    // loop over the needed range
    for (long long i = 1; i <= n; i++) {
        if (pk != pkend && i == *pk) {
            // if i is the next number to omit, move pk to the next omitted
            // number (without adding i to results)
            pk++;
        } else {
            // otherwise, add i to results then move pn to the next element
            *(pn++) = i;
        }
    }

    // print results from narr
    for (long long i = 0; i < (n - k); i++)
        printf("%lld ", narr[i]);
    printf("\n");

    // free karr and narr when done
    free(karr);
    free(narr);

  return 0;
}

不需要大量查找 table，并且由于添加到结果中的数字只会增加，下一个要跳过的数字将始终是 karr 中没有的最小数字' t 已经达到...所以只需要为每个新数字检查 karr 中的一个元素。

上面的代码还假设karr中没有数字在循环中不会被检查，即karr中没有数字超出范围1..n.并且由于缺少错误 checking/handling，如果您给它无效输入或 malloc() 由于某种原因失败，它可能会表现得很糟糕。

有效地创建一个包含 n 个数字的数组，不包括 k 个给定数字

Creating an array of n numbers excluding k given numbers efficiently

c

arrays