2

我必须打印给定子集中不存在的 1 和 n 之间的数字。所有子集都将落在 1 和 n 之间。子集始终按升序排列。例如 n=300 并且用户给出的子集是 (30 到 70) (50 到 100) (150 到 200) 和 (250 到 300) 那么我需要将输出打印为：从 1 到 29、101 到 149 的数字, 201 到 249。

我的方法是：

  1. 取从 1 到 n 的每个数字，并验证它是否存在于任何给定的子集中
  2. 如果它不存在于任何给定的子集中，则打印该数字。
  3. 否则继续。

我的问题是：

  1. 还有比这更优雅的方法吗？
  2. 以及我们如何用 C 语言实现这一点。（我不是要求逐行代码。我只是想知道我们如何在 C 语言中表示子集，以及如何在子集中搜索缺失的数字。）
4

4 回答 4

2

如果 n 是固定的，即它不是由用户输入的，而是可以硬编码的，你可以定义一个这样的数组：

#define N 300
int my_set[N + 1];

然后用 初始化整个数组1，意思是“必须打印这个数字”。然后，当用户输入子集时，将相应的数组元素设置为0。最后扫描数组并打印值为 still 的元素的索引1。

于 2013-09-07T17:55:37.877 回答
1

一种方法是（只需给出伪代码）：

  1. 按对中第一个元素的升序对集合进行排序。（已针对您的情况进行了排序）

  2. 取一个数组并将元素插入其中： 0, p(1,1),p(1,2),p(2,1),p(2,2)....（将为 0， 30,70,50,100,150,200,250,300...对于OP的情况）

  3. 循环遍历数组，同时将计数器（取 i）增加 2。

  4. if(arr[i]<arr[i+1])arr[i]从to 循环arr[i+1]并打印元素。否则在将计数器增加 2 时，转到大于第arr[i+1]th 个元素的元素。

例如：如果数组是：0, 2, 5000, 3, 50, 60, 100, 6000, 6050; 从 5000 开始，以 2 递增，您将跳转到 6050。

这种方法的优点是它不会比较范围内的每个值以打印或不打印，这与检查范围内的每个数字是否打印相比是一个很大的性能提升。在 C 中创建初始数组会有点困难（这在 C++ 中很容易）。

注意：：由于简短的解释，最初可能看起来不清楚和困难，但事实并非如此。

于 2013-09-07T18:17:58.167 回答
0

这是您可以遵循的方法。假设给你

范围为 [1 到 N]，其中 N 可以是可变的（来自用户的输入）/常数（已经固定）。

子集为 Ai[ai, bi]，其中 1<=i<=k。即您有 k 个子集，其中 ai 是下边界，bi 是上边界。

现在开始创建第一个节点为 [1,N] 的树。在算法执行期间的给定时间，在树中，每个叶节点表示没有被任何给定子集覆盖的数字范围，即您必须打印所有叶节点的数字范围。

初始条件
一开始，Tree 只有一个叶节点 [1,N]。即因为我们还没有处理任何子集，所以我们必须打印 1 到 N 之间的所有数字。

终止条件
在算法树的末尾将包含许多叶子。每个叶子将代表未被任何子集覆盖的数字范围。所以你必须打印这些数字作为输出。

算法：

STEP 1: Creating the Tree   
For i = 1 to k  //process for all given subsets
{
    For every leaf node in current tree
    {
        //Let [x,y] is the current leaf node being processed
        1. if(ai>=x && bi<=y) //subset being processed lie inside the leaf being
           processed.
           create nodes [x,ai-x] and [bi+1,y] and attach as child of the leaf node       
           being processed.

        2. if((x<=ai<y) && (bi>y)) //subset overflows towards right
           create a node [x, ai-1] and attach as child to the current leaf node being
           processed.

        3. if((ai<x) && (x<bi<=y)) //subset overflows towards left
           create a node [bi+1, y] and attach as child to the current leaf node being
           processed.
    }
}

STEP 2: Printing the output
//Now the leaf nodes indicate the numbers to be printed.
For each leaf node [x,y] of the resulting tree
{ 
    //you will get some leaf node with x>y
    if(x<=y)
         print the numbers in range [x,y].
}
于 2013-09-07T19:17:36.667 回答
0

我对C不太了解，但是像这样？n作为第一个命令行参数给出，后跟范围，以空格分隔。

C代码：

#include <stdio.h>

int main(int argc, char** argv) {
    int i, j, count = 1, n, lBound, uBound;

    sscanf (argv[1], "%i", &n);

    for (i = 2; i < argc; i += 2)
    {
        sscanf (argv[i], "%i", &lBound);

        sscanf (argv[i + 1], "%i", &uBound);

        if (lBound > count)
            for (j = count; j <= lBound - 1; j++)
                printf("%d ",j);

        count = uBound + 1;
    }

    if (count < n)
        for (j = count; j <= n; j++)
            printf("%d ",j);
}

输出：

C:\c>notPresent 100 20 80
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 81 82 83 84 85 86 87 88 89 90 91
92 93 94 95 96 97 98 99 100

C:\c>notPresent 100 20 80 60 90
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 91 92 93 94 95 96 97 98 99 100
于 2013-09-07T22:37:16.147 回答