给定数组是另一个数组的子序列

Question

构建一个代码来检查 s_array[] 中的一组数字是否是 array[] 的子序列，这意味着 { 1, 5, 4 } 不是 array，而 { 1, 4, 5} 是一个（顺序很重要）

我的代码将首先检查 s_array[] 的第一个元素是否存在于 array[] 中，一旦找到公共元素，它将继续检查 s_array[] 的其余元素是否存在元素也存在于 array[] 中并且顺序相同（其他元素可以在它们之间）

#include <stdio.h>
void main(){
    int s_array[] = { 5, 7, 13 };
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
    int i, Bcount, m, counter = 1, j = 4;
    //i, Bcount and m are loop counters
    //counter will count number of repeated elements
    //j is the number of elements in s_array + 1

    for( i = 0; i <= 15; i++ ){
        if( s_array[0] == array[i] ){ // does the first element exist?
            for( Bcount = 1; Bcount < j; Bcount++ ){ //checking the rest 
                for( m = i; m < 15; m++){
                    if( s_array[Bcount] == array[m] ){
                        counter++;
                        i = m;
                        break;
                    }
                }

            }
        }
        if( j == counter ){
               printf( "B is a sub-sequence of A.\n" );
               break;
        }
        else{
               printf( "B is not a sub-sequence of A.\n" );
               break;
        }
    }
}

老实说，我看不出是算法问题还是我的编码有问题

Answer 1

首先，第一个循环是错误的，因为 i 上升到 15 并且在此索引处您访问 array 越界（未定义的行为）。

那么循环就很简单了。你只需要

一个循环i数组索引和sis_array
如果您在 s_array[si]

array[i]

si

如果i覆盖array、或如果si得到子数组元素的个数(3)
如果si至少为3，则找到子序列

也就是

int s_array[] = { 5, 7, 13 };
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };

 int si,i;
 for (si=0,i=0 ; i<15 && si<3 ; i++) {
    if (s_array[si] == array[i]) si++;
 }

 printf ("Sub was %s\n", si<3 ? "not found":"found");

Answer 2

在您的示例中，问题是循环被外部 if 条件终止：

    if( j == counter ){
           printf( "B is a sub-sequence of A.\n" );
           break;
    }
    else{
           printf( "B is not a sub-sequence of A.\n" );
           break;
    }

在第一个循环周期之后，程序检查此条件并中断。这个条件应该在循环之外。

Answer 3

J 不应该等于 3 并且第一个 fot 循环索引为 14（或者使其严格小于 15 而不是小于或等于）？在您的第二个 for 循环中，j 可能等于 3，并且 s_array[3] 无效。我会尝试类似的东西：

Bcount = 0;
counter = 1;
for( i = 0; i <= 14; i++ ){
    if( s_array[Bcount] == array[i] ){
        counter++;
        Bcount++;
        if(counter == 3){
              printf("Success");
              break;
        }
    }
}

给定数组是另一个数组的子序列

is a given array a sub sequence of another array

c

arrays

nested-loops