查找数组的最小子序列

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)

• let curr= 0
• let lookup=std::unordered_set<int>
• 将所有元素插入 lookup
• 从开始0到n哪里n是你的元素的数组的大小
  • [环]
    • 如果curr + 1没有lookup突破循环
    • 其他设置curr为curr + 1
  • [循环结束]
• 终于回来了 curr + 1

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

• 对数组进行排序(std::sort总是一个不错的选择)
• 将一些变量设置curr为0
• 从₀开始到_n,其中_i是索引i处数组的元素
  • [环]
    • 如果curr + 1不相等,则_i退出循环
    • 其他设置curr为_i
  • [循环结束]
• 终于回来了 curr + 1

伪代码(慢)

• 将一些变量设置curr为0

• 从₀开始到_n,其中_i是索引i处数组的元素

  • [环]
    • 从_j开始到_n其中j=0
      • [环]
        • 如果curr + 1等于_j,则设置curr为_j并跳出此循环
      • [循环结束]
      • 如果curr没有改变,那就突破这个循环
  • [循环结束]

• 终于回来了 curr + 1