创建一个n个数字的数组，有效地排除给定数字k

How can I create an array of numbers starting from 1 and ending to n while not including k given numbers in the array ? For example n=10 k=2 and two numbers for the value of k are 3 and 6 then my array is 1,2,4,5,7,8,9,10.

如何在数组中不包含给定的k个数字的情况下，创建从1到n的数字数组?例如n= 10k =2 k的值是3和6那么我的数组是1 2 4 5 7 8 9 10。

I have to do this for large numbers like when

对于大的数，比如什么时候

1 < n < 10^9

1 < n < 10 ^ 9

then

然后

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

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

For small numbers I tried indexing and then storing it in a different array which took lot of space and time.How can I do it efficiently?

对于较小的数字，我尝试建立索引，然后将它存储在一个不同的数组中，这需要大量的空间和时间。我怎样才能有效地做到呢?

            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;
                }
            }

1 个解决方案

#1

Using n as the end of the range, k as the number of skipped numbers, narr as the array holding the results, and karr as the array holding the numbers to skip: karr need only be k elements long. If karr is sorted, you only need to compare each new number against one element from karr, moving to the next karr when they match and adding the new number to narr when they don't. The following example shows this (but has no error checks):

使用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;
}

There's no need for a huge lookup table, and since the numbers being added to the results only increase, the next number to skip will always be the lowest number in karr that hasn't already been reached... so it's only necessary to check one element from karr for each new number.

不需要庞大的查找表，因为添加到结果中的数字只会增加，下一个要跳过的数字将永远是karr中尚未到达的最低数字……因此，只需要从karr中为每个新数字检查一个元素。

The code above also assumes that there are no numbers in karr that won't be checked in the loop, that is that there are no numbers in karr that are outside the range of 1..n. And because of the lack of error checking/handling, it may behave badly if you give it invalid input or malloc() fails for some reason.

上面的代码还假设在循环中不会检查karr中的任何数字，即在karr中没有超出1..n范围的数字。由于缺乏错误检查/处理，如果您给它输入无效或由于某些原因导致malloc()失败，那么它的行为可能会很糟糕。