c++ - 查找数组的最小子序列

Question

我有一个数组，例如{1,2,4,5,6}。我希望我的函数找到最大可能的数字 X，以便 1,2,...,X-1 中的所有数字都在数组中。在这种情况下，X=3。数组中的数字可以是从 0 到无穷大。

我的尝试是:

int array(int* t, int r) {
    int* a;
    int m=0;
    int i;

    for(i=0;i<=r;i++){
        a[i]=i;
        if(a[i]==t[i])
            m++;
    }
    return m;
}

我想创建一个从 1 到 r 的数组，这是一个数组的长度，充满自然数，即 {1,2,3...} 。然后我想将它与实际数组 t 进行比较。如果有匹配项，请寻找另一个匹配项。

我不知道为什么它不起作用以及如何解决它？

无论如何，代码不起作用，我仍然不知道如何解决这个问题。

仍在寻找答案。

更新:我做了类似的事情:

int array(int* t, int r) {

for(int x=0;x<r;x++){

    for(int y=0; y<r-1;y++){
        if(t[y]>t[y+1]){
            int temp=t[y+1];
            t[y+1]=t[y];
            t[y]=temp;
        }
    }
}
   for (int i = 0; i != r; i++) {
        if (t[i] != (i + 1)) {
            return i + 1;
        }
    }
    return r + 1;
}

然而，当在输入数组中时，我在某些地方有零，例如{5,0,1,2} 函数始终返回 1，无论零放在何处。这是为什么？

Answer 1

你的代码有很多问题

int array(int* t, int r) {
    int* a;
    int m=0;
    int i;

    for(i=0;i<=r;i++){
        a[i]=i;
        if(a[i]==t[i])
            m++;
    }
    return m;
}

• a未初始化，即它不指向您的程序分配的有效内存。你需要做 int *a = new int[r] . 别忘了做delete a在你的函数返回之前
• i应该上升到 r - 1不是r .所以i < r而不是 i <= r

---

这是一些伪代码，概述了解决此问题的可能方法。如果找不到有效范围作为起点，则结果为零。

伪代码(快速，感谢 Kenny Ostrom )

• 让curr = 0
• 让lookup = std::unordered_set<int>
• 将所有元素插入 lookup
• 从 0 开始至 n其中 n是元素数组的大小
  • [循环]
    • 如果curr + 1不在 lookup 中跳出循环
    • 否则设置curr至 curr + 1
  • [循环结束]
• 最后返回curr + 1

伪代码(有点快，取决于你的排序算法)

• 对数组进行排序( std::sort 总是一个不错的选择)
• 设置一些变量 curr至 0
• 从 a₀ 到 a_n，其中 a_i 是数组中索引为 i
  • [循环]
    • 如果curr + 1不等于 a_i 则跳出循环
    • 否则设置curr给_i
  • [循环结束]
• 最后返回curr + 1

伪代码(慢)

• 设置一些变量 curr至 0

• 从 a₀ 到 a_n，其中 a_i 是索引 i 处的数组元素

  • [循环]
    • 从 a_j 到 a_n，其中 j = 0
      • [循环]
        • 如果curr + 1等于 a_j 然后设置 curr到 a_j 并跳出这个循环
      • [循环结束]
      • 如果curr没有改变，则跳出这个循环
  • [循环结束]

• 最后返回curr + 1